Формы логических функций

Пример.

Число S делится на 3 тогда и только тогда, когда сумма цифр числа S делится на 3.

Пример.

Эквивалентность (равнозначность)

Пример.

Если часть записи числа, состоящая из двух последних цифр, делится на 4, то всё число делится на 4.

a = «Две последние цифры записи числа делятся на 4».

b = «Число делится на 4». a → b

Два высказывания эквивалентны (равнозначны), когда их значения истинности одинаковы. Например, эквивалентны высказывания: "железо тяжелое" и "пух легкий" или высказывания: "железо легкое" и "пух тяжелый". Обозначим эквивалентность символом «↔» и запись "a ↔ b" будем читать "a эквивалентно b".

Эквивалентность (равнозначность): сложное высказывание, состоящее из двух простых высказываний – a и b, которое истинно тогда, когда оба высказывания a и b истинны, или когда оба высказывания a и b ложны.

Эквивалентность (равнозначность)
a	b	F = a ↔ b

Словесно функция равнозначности формулируется следующим образом: «a тогда и только тогда, когда b». Высказывание типа «a тогда и только тогда, когда b » можно заменить высказыванием «если a, то b и, если b, то a » (отсюда видна причина, по которой использована двунаправленная стрелка «↔» для обозначения этой функции). Следовательно, функцию «эквивалентность» можно заменить комбинацией функций импликации и конъюнкции: a ↔ b = (a → b) & (b → a) или a ↔ b = (a → b)(b → a).

a = «Число S делится на 3». b = «Сумма цифр числа S делится на 3». a ↔ b

Даны простые высказывания:

а = «Принтер – устройство вывода информации».

b = «Процессор – устройство хранения информации».

с = «Монитор – устройство вывода информации».

d = «Клавиатура – устройство обработки информации».

Определить значение составного высказывания: (a& b) & (c V d) = ab(c+d) =?

Определим на основе знания компьютера истинность простых высказываний: a=1; b=0; c=1; d=0.

Значение составного высказывания: = ab(c+d) = 1&0&(1+0) = 1&0&1=0

Существуют базовые логические функции: отрицание, конъюнкция, дизъюнкция.

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

Элементарные конъюнкции: ab; a; ab.

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

Элементарные дизъюнкции: a+b; a+; a+b+.

Алгебраические выражения могут упрощаться с использованием различных формул (например, x²+2xy+y²= (x+y)²; x²-y²=(x+y)(x-y) и т.д.) вынесением общих элементов за скобки (например, x³+2x²y+xy²=x(x²+2xy+y²) и т.д.) до такой записи, когда невозможно упростить выражение. Аналогичная ситуация существует в алгебре логики – логических выражениях. Более того, в алгебре логики существуют «стандарты», которые определяют форму выражения, при которой выражение невозможно упростить. Такие стандарты описывают выражения алгебры логики, которые называются «форма».

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

Дизъюнктивная нормальная форма: b+ a+.

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

Конъюнктивная нормальная форма: (+b)(a+)(++).

Дата добавления: 2014-01-11