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

Простейшей логической моделью представления знаний является логика высказываний (ЛВ).

Высказывание – это утверждение, значение которого может быть истинным или ложным. Данное значение называется истинностью высказывания.

В логике высказываний определено два истинностных значения:

1 – истина (true);

0 – ложь (false).

Атом – элементарное высказывание, обозначается строчной латинской буквой, например: p, q, f и т.д.

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

Дизъюнкцией (логическим «или», логическим сложением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности (рис?):

x	y	xÚy

Рис.? Таблица истинности для операции дизъюнкции

Конъюнкцией (логическим «и», логическим умножением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:

x	y	xÙy

Отрицанием называется логическая операция, которая произвольному высказыванию x сопоставляет высказывание не x, истинностное значение которого определяется таблицей истинности:

x	ùx

Импликацией называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:

x	y	x®y

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

x	y	x«y

Литералом или литерой называется атом или его отрицание.

Например: p, q, ùl

Рекуррентное определение формул:

1) Атом – это формула

2) Если F – формула, то ùF – формула

3) Если F_1, F₂ - формулы, то F₁ÚF₂, F₁ÙF₂, F₁®F₂, F₁«F₂ – формулы.

Интерпретация формулы – этоотображение, ставящее в соответствии истинностным значениям атомов истинностное значение формулы.

Например:

Пусть имеется формула:

(p®q)Úl;

пусть p=0, q=0, l=0, следовательно, F=1

p=1, q=0, l=0, следовательно, F=0

Формула, истинная при всех интерпретациях, называется общезначимой. Формула, ложная при всех интерпретациях, называется противоречивой. Формулы f и q являются эквивалентными, если они истинны в одних и тех же интерпретациях.

Множество {0,1} (true, false) c определенными на нем операциями конъюнкции и дизъюнкции образует булеву алгебру:

({0,1}, Ú, Ù) – Булева алгебра

Для любых формул F₁, F₂, F₃ справедливы следующие свойства.

A) Коммутативность

F₁ÙF₂ºF₂ÙF₁.

F₁ÚF₂ºF₂ÚF_1..

B) Ассоциативность

(F₁ÚF₂)ÚF₃ºF₁Ú(F₂ÚF₃).

(F₁ÙF₂)ÙF₃ºF₁Ù(F₂ÙF₃).

C) Дистрибутивность

F₁Ù(F₂ÚF₃)º(F₁ÙF₂)Ú(F₁ÙF₃);

F₁Ú(F₂ÙF₃)º(F₁ÚF₂)Ù(F₁ÚF₃).

D) Законы единицы

FÙ1ºF; FÚ1º1;

E) Законы нуля

FÚ0ºF; FÙ0º0;

F) Закон исключённого третьего

FÚùFº1.

«закон» противоречия

FÙùFº0.

G) Законы поглощения

F₁Ù(F₁ÚF₂)ºF₁;

F₁Ú(F₁ÙF₂)ºF₁.

H) Законы де Моргана

ù(F₁ÚF₂)ºùF₁ÙùF_2;

ù(F₁ÙF₂)ºùF₁ÚùF₂.

I) Правила замены

F₁®F₂ºùF₁ÚF₂;

F₁«F₂=(F₁®F₂)Ù(F₂®F₁)º(ùF₁ÚF₂)Ù(ùF₂ÚF₁).

J) ù ùFºF.

Все приведенные выше законы легко доказываются с помощью таблиц истинности.

Дата добавления: 2015-09-06