Теоретическая часть.

1. Понятие высказывания.

Высказывание- это повествовательное предложение, о содержании которого можно сказать истинно оно или ложно.

Обозначения: A, B, C…

На множестве всех высказываний определена функция истинности:На множестве всех высказываний определим функци

ю

Определение 1.

Значение называется логическим значением или значением истинности высказывания А.

2. Логические операции над высказываниями.

Над высказываниями определяются следующие логические операции (логические связки):

1) Отрицание («не») есть операция перехода от высказывания А к высказыванию Ā (A), которое есть высказывание, которое истинно тогда и только тогда, когда A ложно;

2) конъюнкция («и» есть операция перехода от высказываний А и В к есть составному высказыванию высказывание, которое АÙВ, которое истинно тогда и только тогда, когда A и B истинны одновременно;

3) дизъюнкция («или») - переход к составному высказыванию AÚB, которое высказывание, которое является истинным, если истинно хотя бы одно из высказываний А и В;

4) импликация («если…,то») - переход к составному высказыванию А→В, ложному, когда А истинно и В ложно, и истинному в остальных случаях;

5) эквиваленция («необходимо и достаточно», «тогда и только тогда») приводит к составному высказыванию А↔В, которое истинно, если А и В одновременно истинны или одновременно ложны;

6) альтернативная дизъюнкция: А∆В есть - истинно, когда ровно одно из высказываний A и B истинно, в других случаях – ложно.

3. Формулы алгебры высказываний.

Пропозиционной переменной называется переменная, вместо которой можно подставлять конкретные высказывания.

Обозначения: X, Y, Z…

Определение 1.

Формула – это всякий объект, который построен по следующим правилам.

1) Всякая пропозиционная переменная – это формула.

2) Если F и G – формулы, то (F), FÚG, FÙG, F→G, F↔G F∆G тоже являются формулами.

3) Других формул нет.

При записи формул необходимы приоритеты (очерёдность выполнения операций). Такие приоритеты обозначаются скобками. При их отсутствии сначала выполняется отрицание затем конъюнкция, дизъюнкция, потом импликация и эквиваленция. Внешние скобки обычно опускают.

Определение 2.

Формула называется тождественно истинной или тавтологией (тождественно ложной или противоречием), если при любом наборе значений пропозиционных переменных, входящих в нее, она обращается в истинное (ложное) высказывание.

Определение 3.

Формула называется выполнимой (опровержимой), если существует такой набор значений пропозиционных переменных, который обращает эту формулу в истинное (ложное) высказывание.

4. Таблицы истинности.

Мы определили функцию истинности на пропозиционных переменных, но тем самым она определена на любой формуле, поскольку всякая формула F на каждом наборе переменных принимает значение истины или лжи, а значит, соответственно на всяком наборе λ(F) = 1 или λ(F) = 0.

Определение 1.

Таблицой истинности формулы называют таблицу, связывающую логические значения пропозиционных переменных и логическое значение формулы.

Для формулы n переменных количество строк в таблице истинности равно .

5. Равносильность формул.

Определение 1.

Две формулы F и G называются равносильными, если на любом наборе пропозиционных переменных λ(F) = λ(G).

Обозначения: F ≡ G

Теорема 1 (критерий равносильности).

F ≡ G тогда и только тогда, когда формула F↔G является тавтологией.

Обозначим через тождественную истину и через Æ - тождественную ложь.

Основные равносильности алгебры высказываний:

1) коммутативность:

(5.1)

(5.2)

2) ассоциативность:

(5.3)

(5.4)

3) дистрибутивность:

(5.5)

(5.6)

4) ; ; (5.7)

5) ; ; (5.8)

6) ; ; (5.9)

7) законы де Моргана:

; (5.10)

; (5.11)

8) (5.12)

; (5.13)

9) законы поглощения:

(5.14)

(5.15)

10) закон исключенного третьего:

; (5.16)

; (5.17)

11) закон двойного отрицания:

. (5.18)

6. Нормальные формы формул алгебры высказываний.

Обозначим

Определение 1.

Элементарной конъюнкцией (конъюнктом) называется формула вида: ,

а элементарной дизъюнкцией (дизъюнктом) – формула вида: .

Определение 2.

Дизъюнктивно нормальной формой (ДНФ) называется дизъюнкция конечного количества элементарных конъюнкций.

Определение 3.

Конъюнктивно нормальной формой (КНФ) называется конъюнкция конечного количества элементарных дизъюнкций.

ДНФ и КНФ не единственны. Условимся в качестве ответа принимать ту ДНФ (КНФ) из всех возможных, которая содержит наименьшее количество логических операций.

7. Совершенные нормальные формы формул алгебры высказываний.

Определение 1.

Элементарная конъюнкция (дизъюнкция) называется правильной, если в ее составе нет одинаковых переменных.

Определение 2.

Дизъюнкт (конъюнкт) является полным, относительно некоторого набора переменных, если в его составе представлены все переменные этого набора.

Определение 3.

СДНФ (СКНФ) данной формулы называется такая ее ДНФ (КНФ), которая не содержит одинаковых конъюнктов (дизъюнктов), каждый конъюнкт (дизъюнкт) правилен и обладает свойством полноты.

Теорема 1. Любая формула F, не являющаяся тождественной ложью, обладает единственной СДНФ.

Теорема 2. Любая формула F, не являющаяся тавтологией, обладает единственной СКНФ.

Алгоритм перехода от таблицы истинности формулы к ее записи в виде СДНФ:

1) выбрать в таблице такие наборы исходных переменных, на которых истинностное значение формулы равно 1;

2) записать элементарные конъюнкции для выбранных наборов переменных; при этом необходимо руководствоваться следующим правилом: если значение входной переменной в наборе – единичное, то она записывается в прямой форме, если же значение переменной – нулевое, то – в форме отрицания;

3) полученные конъюнкты объединить между собой знаками дизъюнкции.

Алгоритм перехода от таблицы истинности формулы к ее записи в виде СКНФ:

1) выбрать в таблице истинности такие наборы входных переменных, на которых функция истинности формулы принимает нулевые значения;

2) записать элементарные дизъюнкции для выбранных наборов; при этом следует руководствоваться следующим правилом: если значение входной переменной в наборе нулевое, то она записывается в прямой форме, если значение переменной единичное, то – в форме отрицания;

3) полученные дизъюнкты соединить знаками конъюнкции.

8. Логическое следование.

Определение 1.

Говорят, что формула Q логически следует из формулы Р, если Q принимает значение истины на всяком наборе пропозиционных переменных, на котором значение истины принимает формула Р.

Другими словами, если λ (P) = 1, то λ (Q) = 1.

Обозначения: Р Q

Теорема 1.

Q логически следует из P, тогда и только тогда, когда P→Q – тавтология.

Теорема 2(метод резолюций).

Имеет место логическое следование ├ .

9. Логическое следование из группы формул.

Определение 1.

Говорят, что формула Q следует логически из формул , если , при всех тех значениях переменных, при которых (j=1,2,...,n), то есть Q принимает значения истины на каждом наборе переменных, на котором истинно каждое из .

Обозначения: .

Теорема: Логическое следование имеет место тогда и только тогда, когда

является тавтологией.

Алгоритм получения всех неравносильных между собой логических следствий данной формулы F, не являющейся тавтологией:

1) для формулы F построить СКНФ;

2) выписать все полные правильные дизъюнкты;

3) построить всевозможные их конъюнкции.

Указанный набор конъюнкций или самих дизъюнктных одночленов оказывается искомым набором всех логических следcтвий данной формулы F.

Алгоритм получения всех неравносильных между собой посылок для данной формулы F, не являющейся тавтологией.

1) для формулы F построить СКНФ;

2) выписать все недостающие правильные дизъюнкты;

3) построить всевозможные их конъюнкции с данной формулой F.

Указанный набор конъюнкций оказывается искомым набором всех логических посылок данной формулы F.

10. Применение аппарата алгебры высказываний для анализа и синтеза цифровых устройств.

Элементной базой современных цифровых устройств и систем являются цифровые интегральные схемы.

Цифровая интегральная схема– это микроэлектронное изделие, изготовленное методами интегральной технологии (чаще полупроводниковой), заключенное в самостоятельный корпус и выполняющее определенную функцию преобразования дискретных цифровых сигналов.

Для описания работы цифровых интегральных схем, а, следовательно, и устройств, построенных на их основе, используется математический аппарат алгебры высказываний. Возможность его применения для решения задач анализа и синтеза цифровых устройств обусловлена аналогией понятий и категорий этой алгебры и двоичной системы счисления, которая положена в основу представления преобразуемых устройством сигналов.

Простейшие преобразования над цифровыми сигналами осуществляют цифровые интегральные схемы, получившие названия логических элементов.

Определение 1.

Электронный логический элемент, реализующий отрицание в виде определенных уровней электрических сигналов, называют инвертором или логическим элементом “НЕ”.

Обозначения.

На языке цифровой техники инверсия означает, что выходной сигнал (у) противоположен входному (х). Сказанное можно проиллюстрировать временными диаграммами инвертора.

Определение 2.

Логический элемент, реализующий операцию конъюнкции, называют конъюнктором или логическим элементом “И”.

Обозначение.

Замечание.

Логический элемент “И” часто используют для управления потоком информации. При этом на один из его входов поступают сигналы, несущие некоторую информацию, а на другой – управляющий сигнал: пропустить информацию – 1, не пропустить – 0. Логический элемент “И”, используемый таким образом, называют вентиль.

Определение 3.

Условное изображение и временные диаграммы элемента “ИЛИ” приведены ниже.

Определение 4.

Комбинационным цифровым устройствомназывается устройство, выходные сигналы которого однозначно определяются лишь сигналами, действующими (в тот же момент времени) на его входах.

Комбинационные цифровые устройства применяются для выполнения целого ряда логических и арифметических преобразований над входными сигналами и используются в качестве шифраторов, дешифраторов, сумматоров, мультиплексоров и других функциональных узлов.

В общем случае проектируемое устройство может быть представлено в виде черного ящика, имеющего n входов и m выходов. Изначально об этом черном ящике известен лишь требуемый алгоритм его функционирования, т.е. характер связи между входными воздействиями и выходными сигналами (реакциями). Проектирование сводится к определению оптимальной структуры (схемы) цифрового устройства, реализуемой в заданном базисе логических элементов. Поскольку требуемый алгоритм функционирования, в общем случае, может быть реализован с помощью различных схем, то должна быть определена некоторая, оптимальная схема, например, схема, отличающаяся минимумом аппаратурных затрат, т.е. минимальным числом логических элементов.

11. Нечеткие высказывания.

Определение 1.

Пусть задано некоторое непустое множество Х .Нечетким называется множество A, определенное как множество пар вида: , где .

Множество Х называется базовым множеством, а функция называется функцией принадлежности (к Х).

Замечание 1.

Значения функции принадлежности формируются субъективно и могут иметь различный вид для одного и того же субъекта при различных обстоятельствах и настроениях.

Определение 2.

Высказывание A называется нечетким, если допускается, что оно может быть одновременно истинным и ложным (что определяется различными обстоятельствами и настроениями).

Любое оценочное суждение, основанное на неполных или недостоверных данных, является нечетким и сопровождается обычно выражением степени уверенности (или сомнения) в его истинности. Например, утверждение: "Скорее всего, завтра похолодает".

Определение 3.

Мера (степень) истинности нечеткого высказывания A определяется функцией принадлежности , заданной на множестве Х= {"ложь", "истина"}.

Замечание 2.

Четкое истинное высказывание характеризуется функцией принадлежности . Соответственно, ложное высказывание характеризуется функцией принадлежности .

12. Логические операции над нечеткими высказываниями.

Нечеткие высказывания могут быть простыми и составными. Составные высказывания образуются из простых с помощью логических операций, называемых также логическими связками.

1) Результатом отрицания нечеткого высказывания A называется нечеткое высказывание Ā (A), степень истинности которого определяется выражением: ;

2) результатом конъюнкции нечетких высказываний A и B называется нечеткое высказывание АÙВ, степень истинности которого определяется выражением: ; т.о. степень истинности нечеткого высказывания АÙВ определяется наименее истинным высказыванием;

3) дизъюнкция нечетких высказываний A и B приводит к нечеткому высказыванию AÚB, степень истинности которого определяется выражением: ; т.о. степень истинности нечеткого высказывания AÚB определяется наиболее истинным высказыванием;

4) степень истинности «нечеткой импликации» А→В нечетких высказываний A и B определяется выражение: ;

5) эквиваленция нечетких высказываний A и B приводит к нечеткому высказывание А↔В, степень истинности которого определяется выражением: .