Формулы логики высказываний

Понятие формулы

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

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

Алфавитом логики высказываний называется любое непустое множество, содержащее следующие символы: логические переменные x ₁, x ₂,.., x _n; логические связки Ù,Ú,-,®,«, а также символы скобок (,).

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

1 Любая логическая переменная – формула.

2 Если А и В – формулы, то ` А, А Ù В, А Ú В, А ® В, А «В – тоже формулы.

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

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

А | В – штрих Шеффера (антиконъюнкция), т. е. .

А ¯ В – стрелка Пирса (антидизъюнкция), т. е. .

А Å В – “кольцевая сумма” (“логическое сложение”, “сложение по модулю 2”) – .

Для упрощения записи в формулах логики высказываний приняты следующие соглашения относительно расстановки скобок:

1. Внешние скобки не пишутся.
2. На множестве операций логики высказываний вводятся отношения: транзитивное - “быть более сильным” и эквивалентности - “быть равносильным”. Они представлены на рисунке, причем “более сильные” находятся выше, а ‘равносильные” – на одном уровне.

2.2.2. Равносильность формул

Пусть А и В - две формулы и { x₁, x₂,..,x_n } – множество всех пропозициональных (высказывательных) переменных, входящих в эти формулы. Формулы называются равносильными, если при любом распределении истинности значений переменных x₁, x₂,..,x_n они принимают одинаковые значения. Равносильность формул логики высказываний обозначается так А = В.

Различие знаков «и = состоит в том, что символ «является символом формального языка, а символ = обозначает отношение на множестве формул.

Заметим что отношение равносильности, есть отношение эквивалентности, т. к. оно рефлексивно, т. е. А = А, симметрично А = В => В = А и транзитивно А = В, В º С => А = С.

Для любых формул А, В и С справедливы следующие равносильности:

1) А Ù В = В Ù А

2) А Ù А = А

3) А Ù (В Ù С) = (А Ù В) Ù С

4) А Ú В = В Ú А

5) А Ú А = А

6) А Ú (В Ú С) = (А Ú В) Ú С

7) А Ú (В Ù С) = (А Ú В) Ù (А Ú С)

8) А Ù (В Ú С) = (А Ù В) Ú (А Ù С)

9) А Ù (А Ú В) = А

10) А Ú (А Ù В) = А

11)

12)

13)

14) А = (А Ù В) Ú (А Ù` В)

15) А = (А Ú В) Ù (А Ú` В)

16) А «В = (А ® В) Ù (В ® А)

17) А ® В =` А Ú В =

18) А Ú В =` А ® В =

19) А Ù В =

2.2.3. Тождественно – истинные формулы

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

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

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

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

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

Следствия из этих определений:

1. А тавтология тогда и только тогда, когда А является неопровержимым;

2. А тождественно – ложное тогда и только тогда, когда А является выполнимой;

3. А тавтология тогда и только тогда, когда` А тождественно – ложное;

4. А тождественно – ложное тогда и только тогда, когда` А – тавтология.

Наиболее важными тавтологиями являются (А, В, С – произвольные формулы):

2) А Ú` А;

3) А ® А;

4) А ® (В ® А);

5) (А ® В) ® ((А ® В) ® (А ® С));

6) (А ® (В ® С)) ® ((А ® В) ® (А ® С));

7) (А Ù В) ® А; (А Ù В) ® В;

8) А ® (В ® (А Ù В));

9) А ® (А Ú В); В ® (А Ú В);

10) (` В ®` А) ® ((` В ® А) ® В);

11) ((А ® В) ® А) ® А.

2.3. ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

2.3.1. Абстрактное определение булевой алгебры

Алгебра < A; +, ×, ˉ > называется алгеброй Буля, Если для любых a, b, c Î A ее операции удовлетворяют аксиомам:

1. коммутативности

a + b = b + a;

1.2 ab = ba;

2. ассоциативности

2.1. a + (b + c) = (a + b) + c –;

2.2 a (bc) = (ab) c;

3. дистрибутивности

3.1. a (b + c) = ab + ac;

3.2 a + (bc) = (a + b) (a + c);

4. идемпотентности

4.1. a + a = a;

4.2 aa = a;

5. инволюции = а;

6. поглощения

a + (ab) = a;

6.2. a (a + b) = a;

7. де Моргана

= ` a ` b;

7.2. =` a Ú` b;

8. нейтральности

(a + ) b = b;

8.2. a ` a + b = b.

Если обозначить элемент 0 = a`a, а 1 = a +` a, тогда выполняются равенства:`

=1;` 1 = 0; a + 1 = 1; a × 1 = a; a + 0 = a; a × 0 = 0.

Булева алгебра называется вырожденной, если 0 и 1 совпадают. В таком случае a = a × 1 = a × 0 = 0, следовательно, она не содержит никаких других элементов, а, значит, состоит ровно из одного элемента. Всякая невырожденная булева алгебра содержит два нейтральных элемента 0 (нулевой элемент) и 1 (единичный элемент).

В определении булевой алгебры нет указания на существование такой алгебры. Для Рассмотрим конкретные примеры:

1. Двоичная модель.

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

+				×					ˉ

Данная модель является наиболее важной для компьютерных приложений.

2. Модель исчисления высказываний.

А – множество высказываний с логическими операциями конъюнкции, дизъюнкции и отрицания. Обозначая противоречие 0, а тавтологию – 1, можно проверить, что данное множество с указанными операциями является булевой алгеброй.

3. Теоретико–множественная модель.

Пусть А – непустое множество, тогда множество-степень Р (А), является булевой алгеброй, элементами которой служат различные подмножества множества А. При этом операции + булевой алгебры соответствует объединение множеств, операции ∙ – пересечение множеств, а ¯ – дополнение А. При такой интерпретации булевой алгебры выполняются все ее аксиомы. Множества А и Æ являются соответственно единичным и нулевым элементами данной булевой алгебры.

2.3.2. Булевы функции

Рассмотрим еще одну модель булевой алгебры.

Пусть М – произвольная булева алгебра с базисными операциями +, ×, ˉ. Рассмотрим множества n – местных функций: f: Mⁿ ® M, т. е. (x ₁, x ₂,.., x _n) ® f (x ₁, x ₂,.., x _n).

Тогда по определению:

f ₁ + f ₂: (x ₁, x ₂,.., x_n) ® f ₁ (x ₁, x ₂,.., x_n) + f ₂ (x ₁, x ₂,.., x_n);

f ₁ × f ₂: (x ₁, x ₂,.., x_n) ® f ₁ (x ₁, x ₂,.., x_n) × f ₂ (x ₁, x ₂,.., x_n);`

.

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

Две постоянные функции:

0: (x ₁, x ₂,.., x_n) ® 0;

1: (x ₁, x ₂,.., x_n) ® 1.

Они являются соответственно нулевым и единичным нейтральными элементами.

Если булева алгебра М двухэлементна, т. е. содержит два элемента 1 и 0, то булевы функции называются двоичными функциями.

Если в двухэлементной булевой алгебре элементы 1 и 0 интерпретируются как “включено” и “выключено” соответственно, то соответствующие двоичные функции называются переключательными функциями.

Любую логическую функцию можно задать таблицей истинности, в левой части которой выписаны все возможные наборы значений ее аргументов, т. е. x ₁, x ₂,.., x_n, а правая часть представляет собой столбец значений функции, соответствующий этим наборам.

Число всех возможных различных наборов значений n - переменных логической функции f (x ₁, x ₂,.., x_n) = 2 ⁿ (число всех возможных двоичных векторов длины n). Число всех различных функций n – переменных равно числу возможных расстановок 0 и 1 в столбце с 2 ⁿ сторонами, т. е. ½ Р ₂ (n)½= .

Особую роль в алгебре логике играют логические функции одной и двух переменных – унарные и бинарные логичекие операции. Эти функции интерпретируются естественными логическими связками “НЕ”,”И”,”ИЛИ” и т. д. Они широко используются для описания систем, явлений, формализации рассуждений и т. п.

Множества всех логических функций одной переменной P ₂ (1) - унарных логических операций представляется таблицей истинности содержащей 2¹ строк и ½ P ₂ (1)½= 2² = 4 столбцов,

x
Обозначение функций		x	` x

где , – константы 0 и 1 соответственно.

Эти функции не зависят от переменной x и, поэтому, x в этих функциях называется фиктивной (несущественной) переменной для этих функций.

– повторение переменной.

– отрицание переменной.

Множество всех логических функций двух переменных P ₂(2), то есть, бинарных логических операций, представляется таблицей истинности, содержащей ½ P ₂ (2)½= функций, из которых шесть имеют фиктивные переменные.

Обозначение функций

Обозначение функций

– конъюнкция (логическое умножение x₁ × x₂);

– дизъюнкция (логическое сложение x₁ + x₂).

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

Наиболее употребляемыми являются операции ˉ, Ú, Ù, ®, «, Å, ½, ¯. Значение любой логической формулы, содержащей знаки этих операций можно вычислить для любого набора значение переменных, используя выше приведенные таблицы истинности.

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

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

2. По каждой формуле восстанавливается таблица истинности;

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

2.4. НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

2.4.1. Разложение булевых функций

При изучении алгебры логики возникает вопрос: любая ли функция алгебры логики может быть выражена в виде формулы? Или другими словами: можно ли все булевы функции свести к какому-нибудь меньшему числу “элементарных булевых функций”? Ответ на этот вопрос – утвердительный. Например, все булевы функции можно представить в виде композиции только трех функций:

1. Двухместной конъюнкции x ₁Ù x ₂ (логического умножения x ₁ x ₂);

2. Двухместной дизъюнкции x ₁Ú x ₂ (логического сложения x ₁+ x ₂);

3. Одноместная функция отрицания` x.

Для решения поставленного вопроса вводится обозначение , где - параметр равный 0 или 1.

Очевидно, что: .

Выражение называется литерой. Литеры x и` x называется контрарными.

Конъюнктом или элементарной конъюнкцией называется конъюнкция литер.

Дизъюнктом или элементарной дизъюнкцией называется дизъюнкция литер.

Например, формулы и – дизъюнкты; формула` и – конъюнкты.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конъюнктов.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктов. Например, формула: x ` y Ú y z – ДНФ, а формула (x Ú y Ú z)(x Ú z) y – КНФ;

Заметим, что любая формула алгебры логики эквивалентна некоторой ДНФ. В подтверждении этого рассмотрим следующий алгоритм.

Алгоритм приведения формулы к ДНФ заключается в следующем:

3. Выражаем все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания, используя для этого следующие эквивалентности:

, а также определения операций ½, ¯, Å.

4. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания по правилу .

5. Используя закон дистрибутивности , преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения п. 1 – 3, получаем ДНФ данной формулы.

Пример. Приведем к ДНФ формулу .

Для этого проделаем следующее:

1. Выразим логические операции ®, ¯ через операции Ù, Ú,` .

2. В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания

.

3. Используя закон дистрибутивности, приводим формулу к ДНФ: .

Любая формула эквивалентна также некоторой КНФ.

Алгоритм приведения формулы к КНФ:

Этот алгоритм включает в себя п. 1 – 2 приведения формулы к ДНФ, а п. 3 заменяется

3’. Используем закон дистрибутивности

,

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

Пример. Приведем к КНФ формулу

.

Для этого выполним:

1. Преобразуем формулу к формуле, не содержащей знака ®:

1. В полученной формуле перенесём отрицание к переменным и сократим двойное отрицание, т. е.

.

1. По закону дистрибутивности получаем:

Данная формула является КНФ!

Преобразуем далее эту формулу, используя закон дистрибутивности:

Используя закон поглощения, получим:

.

Полученная в результате формула одновременно является ДНФ и КНФ!

2.4.2. Совершенные ДНФ и КНФ

Любая булева функция может иметь бесконечно много представлений в виде ДНФ и КНФ.

Особое место среди них занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

Пусть (x₁,x₂,..,x_n) – набор логических переменных.

Δ = (d₁,d₂,..,d_n) – набор 0 и 1.

Конституентой нуля набора Δ называется дизъюнкт, он обозначается К ⁰ (d₁,d₂,.., d_n) = x₁^1-d1Ú x₂^1-d2 Ú x_n^1-dn.

Конституентой единицы набора Δ называется конъюнкт и обознается К ¹ (d₁,d₂,..,d_n) = x^d1,x^d2,..,x^dn.

Заметим, что К ¹ (d₁,d₂,..,d_n) = 1, [ К ⁰(d₁,d₂,..,d_n) = 0], тогда и только тогда, когда x₁ = d₁, x₂ = d₂,...,x_n = d_n.

СДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых.

СКНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых.

Другими словами, СДНФ (СКНФ) – это ДНФ (КНФ), содержащие в каждом конъюнкте (дизъюнкте) все переменные x_i из набора (x₁,x₂,..,x_n), которые входят ровно один раз либо как x_i, либо как` x_i.

Например:

Формула – конституента единицы К ¹(1,0,1); формула – конституента нуля К ⁰(0,0,1).

Формула x₁ – СДНФ.

Формула – СКНФ.

Формула – не является СДНФ.

Для решения задачи нахождения СДНФ и СКНФ исходной формулы , предварительно рассмотрим разложения булевой функции f (x₁,x₂,..,x_n) по k переменным (x₁,x₂,..,x_k) – называется разложением Шеннона.

Первая теорема Шеннона.

Любая булева функция f (x₁,x₂,..,x_n) представима в виде 1-го разложения Шеннона:

Доказательство:

Заметим, что , тогда и только тогда, когда . Рассмотрим произвольный набор переменных (a₁,a₂,..,a_n) и покажем, что левая и правая части разложения на этом наборе принимают одно и то же значение.

Левая часть дает f (a₁,a₂,..,a_n).

Правая

Аналогично рассуждая можно прийти ко второй теореме Шеннона.

Вторая теорема Шеннона.

Любая булева функция f (x₁,x₂,..,x_n) представима в виде 2-го разложения Шеннона:

При k = n для булевой функции f (x₁,x₂,..,x_n) ¹ 0 из первой теоремы Шеннона получается ее представление в виде СДНФ:

.

Аналогично для булевой функции f (x₁,x₂,..,x_n)¹1 получается ее представление в виде СКНФ:

.

Приведённые формулы позволяют сформулировать теорему о функциональной полноте:

Для любой булевой функции f найдется формула , представляющая функцию f.

Если f 0, то существует представление ее формулой , находящейся в СДНФ:

.

Такое представление единственно с точностью до порядка следования конституент единицы.

Если f 1, то существует представление ее функции j, находящейся в СКНФ, а именно:

и такое представление единственно с точностью до порядка следования конституент нуля.

Пример. Найти СДНФ и СКНФ функции f (x, y, z) заданной таблицей истинности:

X
Y
Z
f (x,y,z)

По теореме о функциональной полноте СДНФ имеет вид:

,

а СКНФ – .

Таким образом, для нахождения СДНФ и СКНФ исходной формулы , составляется ее таблица истинности, а затем по ней строится требуемая совершенная нормальная форма.

При этом, имея, например, СДНФ для функции f можно составить ее таблицу истинности, а затем по ней найти СКНФ . Часто такой способ бывает трудоемким.

Для нахождения СДНФ можно воспользоваться следующим алгоритмом:

1. Сначало формулу приводят к ДНФ.
2. Затем преобразуют ее конъюнкты в конституенты единицы с помощью действий:

а) если в конъюнкты входят некоторые переменные вместе со своим отрицанием, то этот конъюнкт удаляется из ДНФ;

б) если в конъюнкт одна и та же литера x^d входит несколько раз, то удаляются все литеры кроме одной;

в) если в некоторый конъюнкт x₁^d1,.., x_k^dk не входит переменная y, которая должна входить, то этот конъюнкт заменяется на эквивалентную формулу

x₁^d1,.., x_k^dk Ù (y Ú` y) и, применяя закон дистрибутивности получаем ДНФ, содержащую переменную y. Если недостающих переменных несколько, то для каждой из них к конъюнкту добавляется формула вида (y Ú` y);

г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляют только одну из них. В результате получается СДНФ.

Пример. Найти СДНФ для ДНФ .

Данная формула представляет собой ДНФ. После выполнения пунктов 2а) и 2б), получим: . Добавляя недостающие переменные в конъюнкты, получим:

Удаляя дублирующую конституенту единицы, получаем окончательно:

.

Алгоритм приведения КНФ к СКНФ аналогичен алгоритму приведения ДНФ к СДНФ.

2.5. МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ

2.5.1. Проблема минимизации булевых функций

Для всякой булевой функции такой, что ƒ 0 существует ДНФ. Это может быть, например, СДНФ. В общем случае функция алгебры логики может быть представлена в виде ДНФ не единственным образом. В связи с этим возникает возможность выбора более предпочтительной ДНФ, в частности, наиболее простой или минимальной ее реализации.

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

В простейшем случае минимизацию можно осуществить, вы­писав все ДНФ для этой функции и выбрав среди них минимальную. Однако такой метод очень трудоемок. Рассмотрим другие способы решения поставленной задачи.

Элементарная конъюнкция называется импликантой булевой функции ƒ, если .Импликанта называется простой импликантой, если после отбрасывания любой буквы из получается конъюнкция, не являющаяся импликантой функции ƒ. А дизъюнкция всех простых импликант функции ƒ называется сокращенной ДНФ функции ƒ.

ДНФ называется кратчайшей, если она имеет наименьшее число элементарных конъюнкций среди всех ДНФ, эквивалент­ных ей. Для любой заданной функции, сокращенная ДНФ явля­ется единственной. Однако она может быть избыточной из-за того, что сокращенная ДНФ может содержать лишние импли­канты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то полу­ченная ДНФ называется тупиковой. Заметим, что представление функции в тупиковой форме в общем случае неоднозначно. Вы­бор из всех тупиковых форм формы с наименьшим числом вхо­ждений переменных дает минимальную ДНФ (МДНФ).

2.5.2. Метод Квайна

В данном методе для нахождения МДНФ булевой функции вводится три операции.

1) Операция полнового склеивания

2) Операция неполного склеивания

̅

3) Операция элементарного поглощения

Теорема Квайна. Если исходя из СДНФ произвести все возможные операции неполного склеивания, а потом элементарного поглощения, то в результате получается сокращенное ДНФ, т.е. дизъюнкция всех простых импликант.

Пример. Пусть функция ƒ(x,y,z) задана в форме СДНФ

j =x̅yz̅ Ú x̅yz Ú xy̅z Ú xyz̅ Ú xyz

Тогда произведя в два этапа все возможные операции непол­ного склеивания, а затем элементарного поглощения имеем:

j = x̅y (z̅ Ú z) Ú yz̅ (x̅ Ú x) Ú yz (x̅ Ú x) Ú xz (y̅ Ú y) xy (z̅ Ú z) Ú x̅yz̅ Ú x̅yz Ú xy̅z Ú

xyz̅ Ú xyz = x̅y Ú yz̅ Ú yz Ú xzxy Ú x̅yz̅ Ú x̅yz Ú xy̅z Ú xyz̅ Ú xyz = y (x̅ Ú x) x̅y Ú y (z̅ Ú z) Ú xz Ú x̅y Ú yz̅ Ú yz Ú xz Ú x̅yz̅ Ú x̅yz Ú xy̅z Ú xyz̅ Ú xyz = x̅y Ú y Ú xz Ú x̅y Ú yz̅ Ú yz Ú xy Ú

x̅yz̅ Ú x̅yz Ú xy̅z Ú xyz̅ Ú xyz = y Ú xz

Таким образом сокращенная ДНФ функции ƒ задается формулой y Ú xz.

На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в каком склеивании.

Пример. Пусть функция ƒ(x,y,z) задана СДНФ

Тогда, произведя операции полного склеивания, а затем элементарного поглощения получим

Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом: В заголовках столбцов таблицы записываются конституенты СДНФ, а в заголовках строк простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.

Для последнего примера матрица Квайна имеет вид

Импликанты	Конституенты единицы

В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т.е. находит столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант.

В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменных. В указанном примере тупиковая и минимальная ДНФ совпадают и имеют вид

В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюктивных нормальных форм (МКНФ)

2.5.3. Минимизация с помощью карт Карно

При числе переменных, не превышающих четырех, наилучшим методом нахождения МДНФ является построение карт Карно. Данный метод рассмотрим на примере:

Шаг 1. Составляется таблица истинности заданной формулы. Пусть это будет:

x	y	z	f

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

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

Шаг 3. Отметим на карте овалами группы, содержащие единицы. Три овала определяют логическое выражение

f =xy Ú yzÚ xz

Замечания.

Для получения простых логических выражений следует объединять единицы в группы, расположенные в 2, 4, 8 и т. п. соседних квадратах.

Чем крупнее блок, – тем проще логика.

Следует иметь в виду, что в карте Карно для образования блоков единиц стыкуются также ее края, например:

	x y
C D
	0			0

Выделенные квадраты карты Карно описываются выражением .

Другой пример карты Карно.

	x y
00			10
z w
	0			0

Логическое выражение для данной карты Карно -

2.6. ПОЛНОТА И ЗАМКНУТОСТЬ БУЛЕВЫХ ФУНКЦИЙ

2.6.1. Полнота

Ранее отмечалось, что любая функция алгебры логики может быть выражена в виде формулы через элементарные функции x ̅, x ₁ Ù x _2, x ₁ Ú x ₂. Однако, такими свойствами обладают и другие системы элементарных функций.

Система функций {ƒ₁,ƒ₂,…ƒ_n} из P ₂ (множество всех булевых функций) называется (функционально) полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Примеры фундаментально полных систем:

1) P ₂ – множество всех булевых функций – полная система

2) Система { x ̅, x ₁ Ù x _2, x ₁ Ú x ₂} – полная система

Заметим, что система {0,1} не является полной.

Теорема. Пусть даны две системы функций из P ₂ . A = {ƒ₁, ƒ₂…} и B = { g ₁, g ₂…}, относительно которых известно, что система функций A полна и каждая ее функция выражается в виде формулы через функции системы B. Тогда система B является полной.

Опираясь на эту теорему можно установить полноту ряда систем и тем самым расширить список примеров полных систем.

3) Система { x ̅, x ₁ Ù x ₂} является полной, т.к. известно, что 2) полна и .

4) Система { x ̅, x ₁ Ú x ₂} является полной, т.к. полна система 2) и, кроме того, .

5) Система { x ₁ | x ₂} является полной, т.к. взяв за систему A систему 3), а за систему B систему 5) и определив и .

6) Система {0, 1, x ₁ x ₂, x ₁ Å x ₂} является полной. Для этого за систему A берется система 3), а за B – система 6).

При этом: x ₁ Å 1 = x ̅_1, x ₁ x ₂ = x ₁ Ù x ₂

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

2.6.2. Полином Жегалкина

Т.к. формула, построенная в системе 6) состоит из констант 0, 1 и функций x ₁, x ₂ и x ₁Å x ₂, то после раскрытия скобок выражение формулы переходит в полином по модулю 2 (полином Жегалкина).

Теорема. Каждая функция из P ₂ может быть выражена при помощи полинома по модулю 2. Т.е. в виде ƒ(x ₁, x ₂,…, x _n) = x _i1 ∙ x _i2 ∙∙∙ x _in Å с, где в каждом наборе (i₁, i₂,…,i_n) все i _k (k =1,…,n) различны и суммирование ведется по несовпадающему набору значений . Представление булевой функции в виде полинома Жегалкина единственно с точностью до порядка следования слагаемых.

Полином Жегалкина называется нелинейным, если он содержит произведения переменных, и линейным – если он их не содержат.

Для получения полинома Жегалкина булевой функции используются аксиомы булевой алгебры и равенства, выражающие операции отрицания, Ù, Ú через операции Å, ⊙.

x ̅ = x Å 1, x Ù y = xy, x Ú y = x Å y Å xy

Можно доказать тождества:

1) x Å y = y Å x; x ∙ y = y ∙ x

2) (x Å y) Å z = x Å (y Å z); (x ∙ y) ∙ z = x ∙(y ∙ z)

3) x Å x = 0; x ∙ x = x

4) x (y Å z) = x y Å x z

5) 0 Å x = x

6) 0 ∙ x = 0

7) 1 ∙ x = x

8) x Å x ̅ = 1

9) x ∙ x ̅ = 0

Пример. Определить полином Жегалкина для функции

ƒ (x, y, z) = x̅ y̅ z Ú x̅yz Ú x y̅ z̅.

Используя выше приведенные формулы, получим: ƒ (x, y, z) = (x̅ y̅ z Å x̅yz Å x̅ y̅z x̅yz) Ú x y̅ z̅ = (x̅ y̅ z Å x̅yz) Ú x y̅ z̅ = x̅ y̅z Å x̅yz Å x y̅ z̅) Å (x̅ y̅ z Å x̅yz) x y̅ z̅ = x̅ y̅ z Å x̅yz Å x y̅ z̅ Å x̅ y̅z x y̅ z̅ Å x̅yz x y̅ z̅ = x̅ y̅ z Å x̅yz Å x y̅ z̅ = x̅z (y Å y̅) Å x y̅ z̅ = x̅ z̅ ∙ 1 Å x y̅ z̅ = x̅ z̅ Å x y̅ z̅ = (x Å 1) z Å x (y Å 1) (z Å 1) = xz Å z Å (xy Å x) (z Å 1) = xz Å z Å xyz Å xz Å xy Å x = x Å z Å xy Å xyz - полином Жегалкина

Заметим, что если в эквивалентности j Ú ψ = j Å ψ Å jψ формулы j и ψ являются различными конституентами единицы, то их произведения jψ = 0. Тогда j Ú ψ = j Å ψ. Следовательно, для получения полинома Жегалкина из совершенной ДНФ можно сразу заменить Ú на Å.

2.6.3. Замкнутость

Пусть A – некоторое подмножество функций из P ₂. Замыканием A называется множество тех булевых функций, которые представимы в виде формул через функции множества A. Замыкание множества A обозначается [ A ]. Заметим, что замыкание инвариантно относительно операций введения и удаления фиктивных переменных.

Примеры: 1) A = P ₂, т. к. [ A ] = P ₂;

2) A = {1, x ₁ Å x₂ }. Замыканием этого множества будет класс L всех линейных функций, имеющих вид ƒ(x ₁, x ₂,…, x _n) = c ₀ Å c ₁ x ₁ Å c ₂ x ₂ Å…Å c _n x _n, где c _i = 0_i1, причем (i =0,…, n)

Свойства замыкания:

1) [ A ] = A

2) [[ A ]] = [ A ]

3) если A ₁ Ì A ₂, то [ A ₁] Ì [ A ₂]

4) [ A ₁ È A ₂] É [ A ₁] È [ A ₂]

Класс (множество) A называется (функционально) замкнутым, если [ A ] = A.

Примеры.

1) P ₂ – замкнутый класс.

2) L – замкнут, т.к. линейное выражение, составленное из линейных выражений, в свою очередь, является линейным выражением.

В терминах замыкания и замкнутого класса можно определить полноту (эквивалентную исходному определению), а именно: A – полная система, если [ A ] = P ₂.

2.6.4. Теорема Поста

Ответ на вопрос о полноте произвольной системы F булевых функций дает теорема Поста. Для ее формулировки вводятся определения классов Поста.

1) P ₀ – класс булевых функций, сохраняющих 0, т.е. функций ƒ (x ₁, x ₂,…, x _n), для которых ƒ (0,….0) = 0.

2) P ₁ – класс булевых функций, сохраняющих единицу, т.е. ƒ (x ₁, x ₂,…, x _n), для которых ƒ (1,…,1) = 1

3) S – класс самодвойственных функций

Функция ƒ⁺(x ₁, x ₂,…, x _n) называется двойственной по отношению к функции ƒ(x ₁, x ₂,…, x _n), если , т.е. функция, получающаяся из исходной путем замены значения всех переменных и значений функций на противоположные. В таблице истинности заменяется 0 на 1 и 1 на 0.

Например:

1) (x Ú y)⁺ = x Ù y,

2) (x Ù y)⁺ = x,

3) (x ̅)⁺ = x ̅.

Функция ƒ (x ₁, x ₂,…, x _n) называется самодвойственной, если ƒ⁺ (x ₁, x ₂,…, x _n) = ƒ (x ₁, x ₂,…, x _n).

4) М – класс монотонных функций.

Булева функция ƒ (x ₁, x ₂,…, x_n) называется монотонной, если для любых двух наборов (α ₁, α ₂,…, α _n) и (β ₁, β ₂,…, β_n) у которых α_i ≤ β _iдля всех i = 1,…, n следует, что ƒ(α ₁, α ₂,…, α_n) ≤ ƒ (β ₁, β ₂,…, β_n).

5) L – класс линейных функций, т.е. линейных полиномов Жегалкина.

Заметим, что каждый класс Поста замкнут относительно операций замены переменных и суперпозиции, т.е. с помощью этих операций из функций, принадлежащих данному классу можно получить только функции из этого класса.

Теорема Поста. Для того, чтобы система функций F была полной необходимо и достаточно, чтобы она полностью не содержалась ни в одном из пяти замкнутых классов P ₀, P ₁, S, M, L.

Пример ƒ(x, y) = x | y.

Определим, к каким классам Поста относится x | y. Т.к. ƒ(0,0) = 1, а ƒ(1,1) = 0, то и . Т.к. , то . Т.к. ƒ(0,0)> ƒ(1,1), то . Полином Жегалкина для данной функции имеет вид 1Å xy, т.е. эта функция нелинейна, следовательно .

Таким образом, имеем:

ФУНКЦИЯ	КЛАССЫ
P 0	P 1	S	M	L
x | y	Нет	Нет	Нет	Нет	Нет

В силу теоремы Поста функция x | y образует полную систему, т.е. с помощью штриха Шеффера можно получить любую булеву функцию.

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

Каждый базис содержит не более четырех булевых функций.

Примеры:

Следующие системы булевых функций являются базисами:

1) {Ù, -}; {Ú, -}; {→, -}; {|}; {↓}; {↔, Ú, 0}; {Å, Ù, ↔}.

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

2.7. ЛОГИКА ПРЕДИКАТОВ

2.7.1. Понятие предиката

Логика предикатов – это логическая система, представляющая собой развитие алгебры высказываний. В логике предикатов, наряду с высказываниями, рассматриваются высказывательные функции или предикаты.

Предикатом от n переменных называется выражение P (x ₁,…, x_n), которое становится высказыванием при подстановке в него вместо переменных x ₁,…, x_n их значений из множества M ₁,…, M_n соответственно.

Элементы множеств M ₁,…, M_n называются предметами, а переменные. x ₁,…, x_n – предметными переменными.