Введение в логику. Функции алгебры логики. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма

Логических функций двух переменных – 16; они приведены в таблице ниже.

0  0 0  1 1  0 1    1	0    0    0    0    0    0    0    0    1     1    1     1     1     1    1     1 0    0    0    0    1    1    1    1    0     0    0     0     1     1    1     1 0    0    1    1    0    0    1    1    0     0    1     1     0     0    1     1 0    1    0    1    0    1    0    1    0     1    0     1     0     1    0     1

Функции  и  - константы 0 и 1, т.е. функции с двумя несущественными переменными. Переменная  в функции f называется несущественной (или фиктивной), если изменение значения  в любом наборе ,…,  не меняет значения функции. Функции , и , формально различны. Однако принято функции, отличающиеся лишь несущественными переменными считать равными.

Функция  называется конъюнкцией, ее обозначение , ее часто называют функцией И.

Функция  называется дизъюнкцией, ее обозначение , ее часто называют функцией ИЛИ.

Функция  - это сложение по модулю 2, ее обозначение .

Функция  называется эквивалентностью, ее обозначение .

Еще три функции имеют свои названия:

 - импликация, обозначение , читается «если , то »,

 - стрелка Пирса, обозначение ,

 - штрих Шеффера, обозначение .

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

Пусть даны функции,  …, . Функция f, полученная из  с помощью подстановок их друг в друга и переименования аргументов, называется их суперпозицией. Выражение, описывающее суперпозицию и содержащее только символы переменных, скобки и знаки функций, называется формулой над . Примером формулы может служить выражение . Как правило, знаки операций ставятся между аргументами (инфиксная запись), и формулы приобретают привычный вид. Например, если  обозначает дизъюнкцию,  - конъюнкцию,  - сложение по модулю два, тогда выписанная выше формула примет вид:

()(()).

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

В отличие от табличного задания представление данной функции формулой не единственно. Например, если в качестве исходного множества функций зафиксировать множество функций {, , }, т.е. функции И, ИЛИ, НЕ, то функцию штрих Шеффера можно представить формулами

 и , а функция стрелка Пирса – формулами:

             и .

Формулы, представляющие одну и ту же функцию называются эквивалентными или равносильными.

Булева алгебра.

Здесь будут рассмотрены представления логических функций в виде суперпозиций функций И, ИЛИ, НЕ.

Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введем обозначение , . Пусть α – параметр, равный 0 или 1. Тогда , если x = α, и , если .

Теорема. Всякая логическая функция  может быть представлена в следующем виде:

,   (*)

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

Это равенство называется разложением по переменным .

Теорема доказывается подстановкой в обе части равенства (*) произвольного набора всех n переменных. Так как , только когда x = α, то среди конъюнкций  правой части равенства в 1 обратится только одна – та, в которой . Все остальные конъюнкции равны 0. Поэтому получим:

, т.е. тождество □.

Выполним разложение по всем n переменным. При этом все переменные в правой части равенства (*) получают фиксированные значения и функции в конъюнкциях правой части становятся равными 0 или 1, что дает:

,                            (**)

где дизъюнкция берется по всем наборам , на которых f = 1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f.

Соотношение (**) приводит к важной теореме.

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

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

Операции булевой алгебры также часто называют булевыми операциями.

Рассмотрим основные свойства булевых операций.

Ассоциативность:

а) ;          б) .

Коммутативность:

а) ;       б) .

Дистрибутивность конъюнкции относительно дизъюнкции:

.

Дистрибутивность дизъюнкции относительно конъюнкции:

.

Идемпотентность:

а) ;        б) .

Двойное отрицание:

.

Свойства констант:

.

Правила де Моргана:

а) ;       б) .

Закон противоречия:

.

Закон «исключенного третьего»:

Знак & в формулах, там где это не вызывает сомнений, не ставился.

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

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

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

Язык логики предикатов.

Значение логики предикатов, заключается не столько в ее собственных