Тема 1. Алгебра логики высказываний

Формулы алгебры логики

Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.

В качестве примеров высказываний приведем предложения «НГТУ — крупнейший вуз Новосибирска» и «Снег зеленый». Первое высказывание является истинным, а второе — ложным.

Поставим в соответствие высказыванию Р логическую переменную x , которая принимает значение 1, если Р истинно, и 0, если Р ложно.

Если имеется несколько высказываний, то из них можно образовать различные новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные — сложными. Соответственно из логических переменных можно составлять различные конструкции, которые образуют формулы алгебры логики.

Итак, пусть {xi | i ∈ I } некоторое множество логических переменных. Определим по индукции понятие формулы алгебры логики:

1) любая логическая переменная является формулой (называемой атомарной );

2) если φ и ψ — формулы, то выражения φ, (φ ∧ ψ ), (φ ∨ ψ ), (φ → ψ ), (φ ↔ ψ ) являются формулами;

3) никаких других формул, кроме построенных по пп. 1 и 2, нет.

Если формула φ построена из логических переменных, лежащих в множестве {x 1, x 2, …, xn}, то будем писать φ (x 1, x 2, …, xn).

Символы, ∧ , ∨ , →, ↔, использованные в определении, называются логическими операциями или связками и читаются соотвественно: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность.

Введенные в п.2 формулы следующим образом интерпретируются в русском языке: φ — «не φ », (φ ∧ ψ ) — «φ и ψ », (φ ∨ ψ ) — «φ или ψ », (φ → ψ ) — «если φ, то ψ », (φ ↔ ψ ) — «φ тогда и только тогда, когда ψ ».

Вместо φ часто пишут , вместо (φ ∧ ψ ) — (φ & ψ ), (φ · ψ ) или (φ ψ ).

Действия логических операций задаются таблицами истинности, каждой строке которых взаимно однозначно сопоставляется набор значений переменных, составляющих формулу, и соответствующее этому набору значение полученной формулы:

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

Исходя из таблиц истинности для логических операций, можно строить таблицы истинности для произвольных формул.

Пример 1.1. Построить таблицу истинности для формулы

Будем строить таблицу истинности последовательно в соответствии с шагами построения формулы φ:

Легко заметить, что таблица истинности для φ совпадает с таблицей истинности для .

Расширим понятие формулы, введя новые, не менее важные логические операции:

— (φ | ψ ) — штрих Шеффера или антиконъюнкция, по определению (φ | ψ ) ⇌ (φ ∧ ψ );

— (φ ↓ ψ ) — стрелка Пирса или антидизъюнкция, по определению (φ ↓ ψ ) ⇌ (φ ∨ ψ );

— (φ ⊕ ψ )) — кольцевая сумма, логическое сложение или сложение по модулю 2, по определению (φ ⊕ ψ ) ⇌ (φ ↔ ψ ).

Составим, исходя из определений, таблицы истинности для этих трех операций:

Как видно из примера 1.1, даже при составлении несложных формул возникает обилие скобок. Чтобы избежать этого, в алгебре логики, так же как и в арифметике, приняты некоторые соглашения относительно расстановки скобок. Перечислим эти соглашения.

1. Внешние скобки не пишутся. Например, вместо высказывания ((x ∨ y ) → z ) пишется (x ∨ y ) → z .

2. На множестве {, ∧ , ∨ , →, ↔, |, ↓ , ⊕ } вводится транзитивное отношение < «быть более сильным» и отношение эквивалентности ~ «быть равносильным» по правилам, показанным на рис. 6.1.

Рис. 6.1

Согласно этим отношениям недостающие скобки в формуле расставляются последовательно, начиная с наиболее сильных связок и кончая наиболее слабыми, а для равносильных связок расстановка скобок выполняется слева направо.

Функции алгебры логики

Семантически формулы полностью характеризуются таблицами истинности. При этом можно забыть о синтаксической структуре самих формул и иметь дело с таблицами истинности. Таким образом, мы приходим к понятию функции алгебры логики, которое и будет исследоваться в дальнейшем.

Функцией алгебры логики (ФАЛ) от п переменных (x 1, x 2, …, xn) называется любая функция f : {0, 1}n→ {0, 1}, т. е. функция, которая произвольному набору (δ 1, δ 2, …, δ n) нулей и единиц ставит в соответствие значение f (δ 1, δ 2, …, δ n) ∈ {0, 1}.

Функции алгебры логики называются также булевыми функциями, двоичными функциями и переключательными функциями.

Рис. 6.2

Булевой функцией описываются преобразования некоторым устройством входных сигналов в выходные. Предположим, что устройство, показанное на рис. 6.2, имеет п входов x 1, x 2, …, xn, на которые может подаваться или не подаваться ток, и один выход, на который ток подается или не подается в зависимости от подачи тока на входы. При этом значение переменной xi= 1 интерпретируется как поступление тока на i -й вход, а xi= 0 — как непоступление тока. Значение f (δ 1, δ 2, …, δ n) равно 1, если при x 1= δ 1, …, xn= δ nток на выход проходит, и f (δ 1, δ 2, …, δ n) = 0, если ток не проходит.

Например, операции конъюнкции x ∧ y соответствует устройство с двумя входами и одним выходом. При этом значение выхода равно 1, тогда и только тогда, когда оба значения входов равны 1 (рис. 6.3).

Рис. 6.3

Булева функция f (x 1, x 2, …, xn) полностью определяется своей таблицей истинности:

В каждой строке таблицы вначале задается набор значений переменных (δ 1, δ 2, …, δ n), a затем — значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то будем говорить, что формула φ представляет функцию f .

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.

Вектором значений булевой функции f (x 1, x 2, …, xn) называется упорядоченный набор всех значений функции f , при котором значения упорядочены по лексикографическому порядку множества аргументов {0, 1}n.

Булева функция f (x 1, x 2, …, xn), принимающая значение 1 (соответственно 0) на всех наборах нулей и единиц: f (x 1, x 2, …, xn) ≡ 1 (соответственно f (x 1, x 2, …, xn) ≡ 0), называется константой 1 (константой 0).

Эквивалентность формул

Формулы φ (x 1, x 2, …, xn) и ψ (x 1, x 2, …, xn) называются эквивалентными (φ ~ ψ ), если совпадают их таблицы истинности, т. е. совпадают представляемые этими формулами функции

Отметим основные эквивалентности между формулами:

1) ((φ ∧ ψ ) ∧ χ ) ~ (φ ∧ (ψ ∧ χ )), ((φ ∨ ψ ) ∨ χ ) ~ (φ ∨ (ψ ∨ χ )) (ассоциативность ∧ и ∨ );

2) (φ ∧ ψ ) ~ (φ ∧ ψ ), (φ ∨ ψ ) ~ (φ ∨ ψ ) (коммутативность ∧ и ∨ );

3) (φ ∧ φ ) ~ φ , (φ ∨ φ ) ~ φ (идемпотентность ∧ и ∨ );

4) (φ ∧ (ψ ∨ χ )) ~ ((φ ∧ ψ ) ∨ (φ ∧ χ )), (φ ∨ (ψ ∧ χ )) ~ ((φ ∨ ψ ) ∧ (φ ∨ χ )) (законы дистрибутивности );

5) (φ ∧ (φ ∨ ψ ) ~ φ , (φ ∨ (φ ∧ ψ ) ~ φ (законы поглощения );

6) (φ ∧ ψ ) ~ φ ∨ ψ, (φ ∨ ψ ) ~ φ ∧ ψ (законы де Моргана )

7) φ ~ φ (закон двойного отрицания);

8) φ → ψ ~ φ ∨ ψ;

9) φ ↔ ψ ~ ((φ → ψ ) ∧ (ψ → φ ) ~ ( φ ∨ ψ ) ∧ ( ψ ∨ φ );

10) (φ ∨ φ ψ ) ~ (φ ∨ ψ ), ( φ ∨ φ ψ ) ~ ( φ ∨ ψ );

11) φ ( φ ∨ ψ ) ~ φ ψ, φ (φ ∨ ψ ) ~ φ ψ

Формула φ (x 1, x 2, …, xn) называется выполнимой (опровержимой ), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).

Формула φ (x 1, x 2, …, xn) называется тождественно истинной общезначимой или тавтологией (тождественно ложной или противоречием ), если эта формула принимает значение 1 (соответственно 0) при всех наборах значений переменных, т. е. функция f является константой 1 (константой 0).

Если φ — тождественно истинная формула, то будем писать ⊨ φ . В противном случае пишем ⊭ φ .

Таким образом, ⊨ ⊭ x ∧ y , ⊭

Формула φ тождественно ложна тогда и только тогда, когда φ тождественно истинна (⊨ φ );

Формула φ опровержима тогда и только тогда, когда она не является тождественно истинной (⊭ φ );

Формула φ выполнима тогда и только тогда, когда она не является тождественно ложной.

Отметим, что тождественно истинные (соответственно тождественно ложные) формулы образуют класс эквивалентности по отношению ~.

⇐ Предыдущая 9 10 11 12 131415 16 17 18 Следующая ⇒