Теоретические основы. Элементы математической логики

Элементы математической логики

Логика высказываний

Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. Истинность или ложность предложения есть истинное значение высказывания. Сопоставим каждому высказыванию переменную равную 1, если оно истинно и равную 0 если оно ложно. Если P и Q – некоторые высказывания, то можно образовать высказывания “P или Q”, “P и Q”, “не P”, введя операции дизъюнкции (), конъюнкции(&) и отрицания. Действия этих операций задаются таблицами истинности (таб. 1-3), каждой строке которых взаимно однозначно соответствуют набор значений составляющих высказываний и соответствующее значение составного высказывания.

Таблица 1 Таблица 2 Таблица 3

P	Q	P Q		P	Q	P&Q		P

Операции дизъюнкции, конъюнкции и отрицания читаются как «или», «и» и «не».

Приведем основные законы, определяющие эти операции:

закон идемпотентности дизъюнкции и конъюнкции

(1)

закон коммутативности дизъюнкции и конъюнкции

(2)

закон ассоциативности дизъюнкции и конъюнкции

(3)

закон дистрибутивности конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции

(4)

закон двойного отрицания

(5)

законы де Моргана

(6)

законы склеивания

(7)

законы поглощения

(8)

законы Порецкого

(9)

Законы, определяющие действия с константой

(10)

Всякое высказывание, построенное с помощью операций «и», «или», «не», имеет некоторое истинное значение, зависящее от значений составляющих высказываний. Любое высказывание f может быть задано в виде таблицы истинности. Если значение высказывания зависит от n составляющих высказываний x₁,x₂,x₃,…x_n, то таблица истинности содержит 2 ⁿ строк. Составляющие высказывания x_i будем называть атомарными высказываниями или просто переменными x_i, рассматривая при этом сложное высказывание как функцию f от n переменных.

Построение совершенных нормальных форм.

Исчисление высказываний можно построить используя соответствующие таблицы истинности. Алгебра Буля простейшая в классе булевых алгебр; она является двухэлементной булевой алгеброй. Одним из элементов двухэлементной булевой алгебры является 0, так как булева алгебра является решеткой с дополнениями, поэтому вторым элементом этой алгебры является 1.

Каждое высказывание и соответствующую ему булеву функцию f (x₁,x₂,…x_n) можно представить в виде дизъюнкции конституент , где

.

Пример 1. Рассмотрим пример высказывания f(x₁,x₂,x₃), заданное таблицей истинности (таб. 4)

Таблица 4.

Согласно предыдущему утверждению функция f(x₁,x₂,x₃) может быть представлена в виде:

f(x₁,x₂,x₃)= .

В дальнейшем представление булевой функции f(x₁,x₂…x_n) в виде дизъюнкции конституент будем называть совершенной дизъюнктивной нормальной формой (СДНФ) функции f(x₁,x₂…x_n).

Переменную или ее отрицание будем называть первичным термом. Количество первичных термов, которые образуют форму, называют сложностью L(f) этой формы.

Сложность СДНФ функции из примера равна 12. Для уменьшения сложности этой функции используют основные тождества алгебры Буля (законы 1-8). Согласно свойству идемпотентности дизъюнкции имеем:

f(x₁,x₂,x₃)= .

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

f(x₁,x₂,x₃)=

Окончательно имеем

f(x₁,x₂,x₃)=

В результате получаем сложность L(f) функции f(x₁,x₂,x₃) равную 5.

Аналогично можно каждое высказывание и соответствующую ему булеву функцию f (x₁,x₂,…x_n) представить в виде конъюнкции конституент , где

.

В дальнейшем представление булевой функции f(x₁,x₂…x_n) в виде конъюнкции дизъюнкций будем называть совершенной конъюнктивной нормальной формой (СКНФ) функции f(x₁,x₂…x_n).

Для примера 1 функция f(x₁,x₂,x₃) может быть представлена в виде:

f(x₁,x₂,x₃)=

Булевы функции двух переменных

Любое сложное высказывание можно представить в виде выражения, в которое входят простые высказывания (переменные) x_i операции дизъюнкции, конъюнкции, отрицания и, быть может, скобки. Рассмотрим, каким свойствам должны удовлетворять операции, с помощью которых можно выражать любое сложное выражение.

Суперпозицией системы

называется любая функция f, полученная:

а) из переименованием переменных, ;

б) подстановкой вместо некоторых переменных функции функций , ;

в) с помощью многократно применения пунктов а) и б).

Система S называется полной в P_k, если любая функция f P_k представима в виде суперпозиции этой системы; система S называется базисом, если полнота S теряется при удалении хотя бы одной функции, где P_k – k-значная логика.

Построим все булевы функции от двух переменных (таб.5)

Таблица5

Индекс i функциональной переменной f_i, i=0,1,2,….,15, равен десятичному эквивалентному набору значений этой функции, читаемой сверху вниз. Приведем эти булевы функции:

f₀(x₁,x₂)=0 – константа 0;

f₁(x₁,x₂)= конъюнкция;

f₂(x₁,x₂)= - левая коимпликация (читается «не если x_1, то x₂);

f₃(x₁,x₂)= ;

f₄(x₁,x₂)= - правая коимпликация;

f₅(x₁,x₂)=

f₆(x₁,x₂)= - сложение по модулю 2 или функция неравнозначности, неэквивалентности;

f₇(x₁,x₂)= - дизъюнкция;

f₈(x₁,x₂)= - функция Вебба;

f₉(x₁,x₂)= - функция эквивалентности, равнозначности;

f₁₀(x₁,x₂)= - отрицание;

f₁₁(x₁,x₂)= - правая импликация (читается «если x_2, то x₁);

f₁₂(x₁,x₂)= - отрицание;

f₁₃(x₁,x₂)= левая импликация (читается «если x_1, то x₂);

f₁₄(x₁,x₂)= - функция Шеффера;

f₁₅(x₁,x₂)=1– константа 1.

Не нашли, что искали? Воспользуйтесь поиском: