Материал: Shporochki_MLITA

1. Операция дизъюнкция. Логическое сложение, логическое ИЛИ. «или то, или это, или оба сразу» Определение: x+y; СДНФ: ; СКНФ: x+y; ЖИ: ТИ: (0111).

2. Операция конъюнкция. Логическое умножение, логическое И.

Определение: xy; СДНФ: ; СКНФ: ; ЖИ: ТИ: (0001).

3. Операция импликация. Логическая связка, по своему применению приближенная к союзам «если…, то…». Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно.

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (1101).

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

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (1001).

5. Операция исключающее или. Сложение по модулю 2. В случае двух переменных результат выполнения операции является истинным тогда и только тогда, когда один из аргументов является истинным, а второй ложным. Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов, равных 1, составляющих текущий набор, — нечётное.

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (0110).

6. Операция отрицание. Логическое НЕ. Операция, результатом которой является суждение (в известном смысле) «противоположное» исходному.

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (10).

7. Операция Штрих Шеффера. Таким образом, высказывание означает, что X и Y несовместны, то есть не являются истинными одновременно.

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (1110).

8. Операция стрелка Пирса. Таким образом, высказывание «X ↓ Y» означает «не max (X,Y)». От перемены мест операндов результат операции не изменяется.

Определение: ; СДНФ: ; СКНФ: ; ЖИ: ТИ: (1000).

9. СДНФ. Формула имеет совершенную дизъюнктивную нормальную форму (СДНФ), если выполнены следующие условия: 1) F имеет ДНФ; 2) каждая элементарная конъюнкция ДНФ содержит один и только один из литералов или для любого 3) F не содержит одинаковых элементарных конъюнкций; 4) упорядочена в lex. Методы построения: 1) Алгебраические преобразования: шаг 1) приводим формулу к ДНФ. Шаг 2) Если в полученной ДНФ какая-то элементарная конъюнкция С не содержит ни переменной , ни ее отрицания для то равносильными преобразованием заменяем С на две элементарные конъюнкции . Шаг 3) Если элементарная конъюнкция С содержит два вхождения одного литерала, то одно из них вычеркиваем. Если же конъюнкция С содержит для любого то вычеркиваем всю элементарную конъюнкцию. Шаг 4) Если полученная формула содержит одинаковые элементарные конъюнкции, то оставляем одну из них, а остальные вычеркиваем. 2) По ТИ: шаг 1)Составим ТИ формулы . Шаг 2) Выделим строки таблицы, в которых в столбце F стоит 1. Шаг 3) Каждой выделенной строке поставим в соответствие элементарную конъюнкцию. Шаг 4) Составим дизъюнкцию, определенных на шаге 3 элементарных конъюнкций. Пример: ;

10. minДНФ. ДНФ называют минимальной, если она содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей ДНФ. Методы построения: 1) метод минимизирующих карт: шаг 1) оставляем только строки, содержащие СЭК, присутствующие в СДНФ; шаг 2) В оставшихся строках вычеркиваем ЭК, которые уже вычеркнуты; шаг 3) В каждой невычеркнутой строке оставляем ЭК только минимальной длины; шаг 4) В каждой невычеркнутой строке выбираем по одной ЭК, составляем таким образом все возможные ДНФ, упрощаем их и выбираем min. 2) Алгебраические преобразования.

Пример: MinДНФ:

11. СКНФ. Формула имеет совершенную конъюнктивную нормальную форму (СКНФ), если выполнены следующие условия: 1) F имеет КНФ; 2) каждая ЭД содержит один и только один из литералов или для любого ; 3) F не содержит одинаковых ЭД. Методы построения: 1) Алгебраические преобразования: шаг 1) Приведем формулу к КНФ. Шаг 2) Если в полученной на первом шаге КНФ какая-либо ЭД D не содержит ни переменной ни для , то равносильным преобразованием заменяем D на две ЭД: Шаг 3) Если ЭД D содержит два вхождения одного литерала, то одно из них вычеркиваем. Если же дизъюнкции D содержит и для , то вычеркиваем всю ЭД. Шаг 4) Если полученная формула содержит одинаковые ЭД, то оставляем одну из них, а остальные вычеркиваем. 2) По ТИ: шаг 1)Составим ТИ формулы . Шаг 2) Выделяем строки таблицы, в которых в столбце F стоит 0. Шаг 3) Каждой выделенной строке поставим в соответствие ЭД. Шаг 4) Составим конъюнкцию, определенных на шаге 3 элементарных дизъюнкций. Пример: ; =( )(X )( )=( )( )( )( )(X )(X ).

12. Полином Жегалкина. Рассмотрим полный класс . Очевидно, что его замыкание содержит многочлены (от любого числа переменных) над полем . Эти многочлены называют полиномами Жегалкина. Поскольку для элементов справедливо тождество то полином Жегалкина можно записать в виде: и суммирование ведется по всем подмножествам множества {1,…,n}. Методы построения: 1) Алгебраические преобразования; 2) Методом неопределенных коэффициентов. Пример:

13. Двойственная функция.

 Булева функция f*(x1, …, xn) называется двойственной булевой функции f(x1, …, xn), если она получена из f(x1, …, xn) инверсией всех аргументов и самой функции, то есть

Пример:

По опр

По теор

14. Теорема о построении двойственной функции от суперпозиции. Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций.

Формула F* называется двойственной формуле F, если она получена из F заменой символов функций на символы двойственных им функций.

По опр

По теор

Для

15. Самодвойственная функция.

Самодвойственная функция — булева функция, двойственная сама к себе. 

Критерий: У самодвойственной функции ТИ кососимметрична (на симметричных местах противоположные значения)

Достаточное условие НЕсамодвойственности булевой функции. Если число единиц в столбце значений функции не совпадает с числом нулей, то функция не является самодвойственной.

Примеры:

Не самодвойственная

Самодвойственная

16. Выводимость: определение. Приведите пример пары высказываний и третьего, выводимого из них, выводимость обоснуйте.

Определение (выводимость): ; - логическое следствие Обозначение: .

Другое определение:

Пример: Доказать построением ТИ.

16. Выполнимость: определение. Приведите примеры выполнимого и невыполнимого наборов высказываний, ответ обоснуйте.

Набор функций называют выполнимым: выполнимый

Проверить выполнимость множества формул (например F1,F2,F3) можно построением совместной таблицы истинности этих формул. Если найдется хотя бы одна строка, в которой в столбцах формул (F1, F2, F3) стоят единицы, то это множество выполнимо. Если такой строки нет, то множество формул невыполнимо. Выполнимо: Для невыполнимого аналогично построить, только с наличием нулей в строках функций.

16. Резольвента: определение. Связь резольвенты и выводимости. Приведите пример набора высказываний, для которого множество всех возможных резольвент состоит из не менее четырех различных элементов.

Дизъюнкт называют резольвентой дизъюнктов . Пусть D₁=B₁vA , D₂=B₂v¬A - дизъюнкты. Дизъюнкт B₁vB₂ называется резольвентой дизъюнктов D₁ и D₂ по литере А и обозначается через res_A(D₁,D₂).

Резольвента является логическим следствием порождающих ее дизъюнктов.

Пример: множество дизъюнктов . Пример резольвенты Res= .

16. К каким задачам применим метод резолюций в логике высказываний? Алгоритм решения задачи методом резолюций.

?Особенность метода состоит в том, что он оперирует не с произвольными формулами, а с дизъюнктами.

Алгоритм: Шаг1) Составляем множество формул . Шаг2) Каждую из формул множества Т приводим к КНФ. Шаг3) Разбираем КНФ на элементарные дизъюнкты. Шаг4) Строим все возможные резольвенты набора ЭД, полученного в 3 пункте.

16. Приведите пример решения задачи логики высказываний методом резолюций.

Шаг1) Шаг2) Шаг4) Res( )=B:= Res( )=C:= Res( )=0.