21. Проблема разрешимости в алгебре высказываний.

В логике высказываний (ЛВ) рассматрив-ся предложения, отн-но к-ых м. однозначно сказать явл-ся ли они истинными или ложными. Такие предл наз-ся высказываниями.

X,y,z – переменные высказывания, они м. принимать значения истина или ложь.

Над высказываниями м .вып-ть разл. Логич. Операции и получать новые высказывания:

1. кконъюнкция (^) – операция, с пом кот м.построить новое высказывание х^y, из к-го истинность опр-ся след.образом:данное высказывание истинно только тогда, когда оба выск х и у б.истинны.

^ обычно наз-ся логическим умножением.

2. дизъюнкция (v, логич сложение) – логич оп, с пом к-ой для высказываний х и у м.построить новое высказ-е х v у, к-е принимает значение ложь только тогда, когда оба высказывания ложные.

3. импликация (→) – оп, с пом к-ой для высказываний х и у м. построить новое высказ х→у, к-е принимает значение ложь тогда, когда х – истина, а у – ложь.

4. эквиваленция(↔) – оп, с пом к-ой м.построить новое выск-ние х↔у, истинность к-го опр-ся сл.образом: оно истинно только тогда, когда х и у принимают одинакове зна-я истинности.

5. отрицание(⌐,−) – оп, с пом к-ой строится новое выск х (с чертой)(отрицание х), истинность к-го опр-ся сл.образом: если х – истина. То новое выск – ложно. И наоборот

С пом лог операций из 2-х выск-ний м.построить новое высказывание. С ноыми выск-ями м. также вып-ть лог оп и т.д.

Т.о. приходим к понятию формулы высказываний(ФЛВ)

Исп-ся сл. Договоренности:

1 по силе лог оп будут вып-ся в след.порядке, если нет скобок: ^,v,→,↔

2 внешние скобки в формуле м.опускать

3 если в формуле есть отрицание, то сначала вып-ся все оп под знаком отрицания, а потом – само отрицание.

Алгебра высказываний – это сов-ть формул, сведенных к логич-м оп-ям. Для к-ых вып-ся список законно основных равносильностей на мн-ве данных формул. (2 формулы равносильны, если они принимают одинак

значения истинности на одних и тех же наборах переменных высказываниях, от к-ых зависит формула). Такие формулы наз-ся законами АВ:

1 х≡х (х равносилен сам себе)

2 x(c двойным отрицанием)≡х

3 x v л≡х, х^и≡х, x v и≡и, х^л≡л

4 переместительный закон: х^у≡ у^х, x v у≡ у v х

5 (х↔у)≡(х→у)^(у→х)

С пом законов AИ м.переходить от одной формулы к др, делая при этом равносильные преобразования.

Проблема разрешимости в АВ формулируется сл.образом: можно ли указать а-м для любой формулы АВ, с пом к-го м.опр-ть явл-ся ли ф-ла тождественно истинной, тождественно ложной или только выполнимой. Опр. Ф-ла тожд-но истинна, если она принимает зн-е истинна на любом наборе переменных высказываниих х1,х2, …, хn Опр. Ф-ла тожд-на л, если она принимает зн-е ложь на любом наборе пер. Опр. Ф-ла выполнима, если существует хотя бы один набор зн-ний пер-ys[? От к-ых щависит ф-ла. На к-ом ф-ла принимает зн-е и. Проблема разрешимости решается в АВ положительно. М.указать неск-ко таких а-мов:

1) построение таблицы истинностей

2) связан с равносильными преобразованиями

Опр. Элементарная ^ - ф-ла АВ, к-ая предст собой ^ переменных или их отрицаний Опр. ДНФ (диз.нормальная форма) – ф-ла АВ, к-ая предст.собой дизъюнкцию элем-х ^. Опр. Элементарная дизъюнкция - ф-ла АВ, к-ая предст собой диз. переменных или их отрицаний. Опр. КНФ - – ф-ла АВ, к-ая предст.собой ^ элем-х дизъюнкций.

Среди мн-ва ф-л выд-ют:

1. СДНФ – ф-ла, к-ая обладает след.св-ми:

   1. явл ДНФ

   2. элемент. ^ различны

   3. элем-ная ^ сод-ит ровно n элементов

Смысл: любая ф-ла АВ, если она не явл-ся тожд-но л, м.б. однозначно приведена к СДНФ.

По аналогии CКНФ

Рассмотрим построение СДНФ и СКНФ по таблице истинностей(на пр-ре F(x,y,z))

А-м построения СДНФ:

1) Выбираем в таблице строки, в к-ых ф-ла принимает зн ИСТИНА (1,2,4,7)

2) Для каждой из выделеннх строк строим элем ^

1 – x^y^z 2 – x^y^⌐z 4 - ⌐x^y^z 7 – ⌐x^⌐y^z

3) Построенные элем. ^ объединяют операцией дизъюнкция.

Получаем СДНФ:

(x^y^z)v(x^y^⌐z)v(⌐x^y^z)v(⌐x^⌐y^z) – СДНФ

А-м построения СКНФ:

1) Выбираем в таблице строки, в к-ых ф-ла принимает зн ЛОЖЬ (3,5,6,8)

2) Для каждой из выделеннх строк строим элем диз (если переменная истинна, то с отрицанием)

3 – ⌐x v y v ⌐z 5 – ⌐x v y v z 6 – x v ⌐y v z 8 – x v y v z

3) Построенные элем. диз строим КНФ. Получаем СКНФ:

(⌐x v y v ⌐z)^( ⌐x v y v z)^( x v ⌐y v z)^( x v y v z) – СКНФ

С пом.СДНФ ф-лу м.исследовать на проблему разрешимости: если ф-ла от n переменных явл СДНФ, то ф-ла не явл тожд-но Л. Если она сод-т 2ⁿ элем-х ^, то ф-ла тожд.И. Если сод-т < 2ⁿ - ф-ла выполнима

С пом CКНФ м. исследовать на проблему разрешимости : если CКНФ построена, то ф-ла не явл тожд-но И. Если она сод-т 2ⁿ элем-х диз, то ф-ла тожд.И. Если сод-т < 2ⁿ - ф-ла выполнима