Доказательство дистрибутивности дизъюнкции относительно конъюнкции
Оглавление:
2.5. Дизъюнктивные и конъюнктивные нормальные формы булевых функций
Получаем СКНФ. Пример 1. Постройте КНФ функции
.
Решение Исключим связку «
» с помощью законов преобразования переменных: = законы де Моргана и двойного отрицания/ =
/дистрибутивные законы/ =
. Пример 2. Приведите к ДНФ формулу
. Решение Выразим логические операции
и
через
,
и
:
Доказательство таблицы истинности дистрибутивного закона
Операнды и результаты некоторых побитовых операций X У х & у X v у X IMP y .x EQV y х XOR y Логические операции.
NOT. Поразрядный оператор not (he), или дополнение, является одноместной операцией, которая выполняет логическое отрицание на каждом бите, формируя дополнение данного бинарного значения. Биты, содержавшие бывшие «0», устанавливаются в «1»; и наоборот.
Например: 1000 = NOT 0111 Во многих языках программирования (включая С), поразрядный оператор not обозначается как «~» (тильда).
Этот оператор не следует путать с «логическим отрицанием» («!» — восклицательный знак), который обрабатывает все значение как отдельное булевское.
Билет № 11. Дизъюнкция высказываний и её свойства (доказательство одного из них).
Отрицание высказываний и его свойства (доказательство одного из них). Билет № 13. Импликация высказываний и её свойства (доказательство одного из них).
Обратная, противоположная и обратная противоположной импликации. Импликацией двух высказываний A и B называется новое высказывание A=>B(из А следует В, если А то В),которое ложно только в том случаи, когда А-ИСТИНА,В-ложь, во всех остальных случаях! Импликация-истина А В A=>B И И И И Л Л Л И И Л Л И Свойства: 1.закон контропозиции A=>B ó В =>A A B A=>B В A В => A И И И Л Л И И Л Л И Л Л Л И И Л И И Л Л И И И И Если дана импликация A=>B ,то импликация В=>A называется обратной A=>B противоположной данной В =>A обратно — противоположной данной.
Эквиваленция высказывания — …двух высказ. a и b,называется новое высказывание A<=>B,которые
Свойства операций над высказываниями
5.
;
;
; 6.
(или
) (закон исключенного третьего);
(или
(закон противоречия); 7.
(или
);
Основы алгебры логики
При нарушении этого закона возможны логические ошибки. Например, рассуждение Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык, значит, теперь смело могу идти в Киев неверно, так как первое и второе слова «язык» обозначают разные понятия.
В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу. Закон непротиворечия: В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.
Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего: 1. Число 12345 либо четное, либо нечетное, третьего не дано.
2. Предприятие работает убыточно или безубыточно.
Формулы и законы логики
Поэтому будем использовать «натуральные» названия.
; 2) если
и
– формулы, то формулами также являются выражения вида
.
Никаких других формул нет. В частности формулой является любая логическая операция, например логическое умножение
. Поскольку
–
Дистрибутивности закон
и A / (B & С) экв.
«для всякого x справедливо свойство Φ или свойство Ψ»
не следует высказывание «для всякого x справедливо свойство Φ или для всякого x справедливо свойство Ψ», хотя обратное следование и имеет место).
Операция же связывания переменной квантором существования дистрибутивна относительно дизъюнкции: (т.е. высказывания «существует такое x, для к-рого верно Φ или Ψ» и «существует такое x, для к-рого верно Ф, или существует
Тавтологии логики предикатов
Теорема 21.8. Всякая формула, получающаяся из тавтологии алгебры высказываний заменой входящих в нее пропозициональных переменных произвольными предикатными переменными, является тавтологией логики предикатов.Доказательство.
Пусть
— тавтология алгебры высказываний иявляются предикатные переменные. Подставим их в данную формулу вместо пропозициональных переменных соответственно.
Получим формулу логики предикатов: .
Если теперь вместо предикатных переменных подставить произвольные конкретные предикаты , то формула превратится в конкретный предикат . Этот предикат тождественно истинный, потому что подстановка вместо предметных переменных любых конкретных предметов из соответствующих множеств превращает данный предикат в высказывание , которое может быть получено также в результате подстановки в исходную тавтологию алгебры высказываний вместо пропозициональных переменных конкретных высказываний соответственно и потому истинно.
Свойства операций конъюнкции и дизъюнкции
• Рассмотрим взаимосвязь операций конъюнкции и дизъюнкции с кванторными операциями.
Пример 3.3.3. Определим значения двух формул:
Сформулируем предложения, выражаемые этими формулами. Р = «Любое действительное число больше 0 или меньше 1».
Q =
«Любое действительное число больше 0 или любое действительное число меньше 1»
. Предложение Р истинно, так как всякое действительное число попадет в интервал (-оо; 1) или (0; +оо), поскольку их объединение даст все множество R Предложение Q ложно, так как оба высказывания УдгеН(д>0) и VagR(xложны.
Действительно, существование отрицательного числа х=- опровергает первое утверждение, а существование числа х=2 опровергает второе утверждение. Итак, предложения Р и Q не равносильны.
• Этот пример показывает, что формулы V.* (А(хУ/В(х)) и /дЛ(д)у/д?(д) (в общем случае) не равносильны.