Алгебра логики Основные понятия

Введение Буль (Boole) Джордж ( , Линкольн, , Баллинтемпл близ Корка), английский математик и логик. Не имея специального математического образования, в 1849 стал профессором математики в Куинс-колледже в Корке (Ирландия), где преподавал до конца жизни. Б. почти в равной мере интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона.

Высказывание Высказывание – любое утверждение, рассматриваемое только с точки зрения его истинности или ложности Простое – значение его истинности не зависит от значений истинности других высказываний Сложное – значение его истинности зависит от других высказываний

0 и 1 Эрнст Шрёдер (нем. Ernst Schröder, 25 ноября1841, Мангейм 16 июня 1902, Карлсруэ) немецкий математик и логик. Известному немецкому математику и логику Эрнесту Шредеру пришло в голову предложить в качестве знака для обозначения ложного суждения цифру 0, что, конечно, привело к обозначению истины цифрой 1.

Булева переменная M={0,1}, где 0 – ложь, 1 – истина. Обычно булевские обозначаются маленькими латинскими буквами. Двоичной, булевой функцией от набора двоичных переменных называется функция, результатом которой могут быть только значения 0 и 1.

Таблицы истинности xG1G2G3G

Операции Функция - это однозначное отображение, преобразование набора аргументов из области определения в значение из области значений. Унарная операция - операция над одним операндом Бинарная операция – операция над двумя операндами

Основные функции Инверсия Логическое «НЕТ», «НЕ» xf (x) f (x)=

Основные функции Конъюнкция Логическое «И» Обозначение: &, ·, xyf (x, y)

Основные функции Дизъюнкция Логическое «ИЛИ» Обозначение: +, xyf (x, y) f (x, y)=(0111)

Дополнительные функции Импликация «если»-«то» xyf (x, y) f (x, y)=(1011)

Дополнительные функции Эквивалентность, равнозначность. Записывается, как x ~ y, логическое равенство. xyf (x, y) f (x, y)=(1001)

Дополнительные функции Сложение по модулю два, неравнозначность. Записывается, как x y, или ¬( x y) XOR (eXclusive OR) xyf (x, y) f (x, y)=(0110)

Дополнительные функции Стрелка Пирса, функция Вебба, логическое «или- не».Записывается, как x y xyf (x, y) f (x, y)=(1000)

Дополнительные функции Штрих Шеффера (И-НЕ) – xyf (x, y) f (x, y)=(1110)

Приоритет операций 1. Инверсия 2. Штрих Шеффера 3. Стрелка Пирса 4. Конъюнкция 5. Дизъюнкция 6. Сложение по модулю 2 7. Импликация 8. Эквивалентность

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

Равносильность Формула A называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Например, x x. если формулы A и B равносильны, то формула A~B - тавтология, и обратно, если формула A~B - тавтология, то формулы A и B равносильны.

Основные равносильности Закон тождества: x=x Закон идемпотентности (повторное применение не даёт ничего нового). x 1 = x, x 1 = 1, x 0 = 0, x 0 = x, Закон противоречия: x x=0 Закон исключенного третьего: x x =1

Основные равносильности Закон снятия двойного отрицания Закон поглощения

Докажем один из законов поглощения Рассмотрим формулу A x (y x). Если в этой формуле x=1 то, очевидно, y x=1 и тогда x (y x)=1 как конъюнкция двух истинных высказываний. Пусть теперь в формуле x=0. Но тогда по определению операции конъюнкции будет ложной конъюнкция x (y x). Итак, во всех случаях значения формулы A совпадают со значениями x, а поэтому A x.

Свойства функций x~y (x y) (y x); x y x y; Правила де Моргана:

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

Основные законы Свойство дистрибутивности Свойство коммутативности Свойство ассоциативности

Булевские функции Функции, принимающие значений 1 и 0, и каждый n их аргументов принимает значение 1 и 0. Записывается, как y = f(x 1, x 2,…, x n ), x 1 {0,1}, x 2 {0,1},…, x n {0,1}, y {0,1}. Теорема: для n существует ровно различных функций n – переменных. Это есть мощность функции n переменных.

Суперпозиция функций Суперпозицией булевых функций f 0 и f 1,..., f n называется функция f(x 1,...,x m )=f 0 (g 1 (x 1,...,x m ),...,g k (x 1,...,x m )), где каждая из функций g i (x 1,...,x m ) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f 1,...,f n.

Пример суперпозиции f(x,y) = ¬(x & y) суперпозиция функций ¬ и & g(x,y) = x Е (x Ъ y) суперпозиция функций Е и Ъ h(x,y,z) = (x & y) Е z суперпозиция функций Е и &.

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

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

Конституэнта нуля Дизъюнктивный терм (или макстерм, или конституэнта нуля) – терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции. Любой дизъюнктивный терм равен нулю только на одном наборе переменных. 0 0 =1; 0 1 =0; 1 0 =0; 1 1 =1.Таким образом, х у =1 тогда и только тогда, когда х = у.

Дизъюнктивная нормальная форма (ДНФ)

Конъюнкти́вная норма́льная фо́рма (КНФ)

Переход от ДНФ к КНФ и наоборот

Переход от ДНФ к СДНФ

Переход от КНФ к СКНФ

Лемма Любая логическая функция f(x 1, x 2, …, x n ) может быть представлена в виде дизъюнкции 2 п дизъюнктных слагаемых, причем дизъюнкция берется по всевозможным наборам из E n. Этот факт будем записывать следующим образом: (*) где дизъюнкция проводится по всевозможным наборам (s 1, s 2, …, s п ) из Е п.

Теорема Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х 1,х 2, …,х n ), для которых f(х 1,х 2, …,х n )=1, и составляем простую конъюнкцию для этого набора так: если х i = 0, то берем в этой конъюнкции !х i, если х i = 1, то берем х i. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ.

Следствие Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание

Нахождение формулы по таблице истинности f (x, y) yx

Нахождение формулы по таблице истинности f (x, y) yx

Теорема По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х 1, х 2, …, х п ), для которых f(x 1, x 2,…, x n ) = 0, причем если х i = 1, то в этой дизъюнкции берем !х i, если же х i = 0, то берем х i.

Штрих Шеффера отрицание дизъюнкция конъюнкция

Стрелка Пирса Через стрелку Пирса могут быть выражены все другие логические операции: ¬x xx x & y (xx) (yy) x y (xy) (xy) Системы из одной функции принято называть универсальным базисом.

Классы ФАЛ Класс функций, сохраняющих константу 0 – K 0 : f(0,0,…,0)=0 Класс функций, сохраняющих константу 1 – K 1 : f (1,1,...,1)=1 Класс самодвойственных функций – V: функции f*(x1,x2,…,xn) двойственная для (K) f(x1,x2,…,xn), если имеет место равенство Функция самодвойственная, если Другими словами самодвойственная функция на противоположных друг другу наборах значений аргументов принимает противоположные значения. Класс линейных функций – L: f(x 1,x 2,…,x n )=С 0 С 1 *x 1 … C n x n, где С – константы Класс монотонных функций – M: Класс симметричных функций – S: функция называется симметричной, если ее значение не меняется при любой перестановке аргументов. f(0,1,0)=f(1,0,0)=f(0,0,1)

Теорема Поста (теорема о пяти «нет»)

Базисы Система функций S1={¬,&,v} образует базис. Для приведения булевой функции к виду содержащему лишь связки из базиса S1 могут быть полезны следующие эквивалентности: XY=¬XvY XY=(Xv¬Y)(¬XvY) X Y=¬XYvX¬Y X|Y=¬Xv¬Y XY=¬X&¬Y

Базисы Система S2={¬,&} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение XvY=¬(¬X&¬Y). Система S3={¬,v} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1, а затем использовать соотношение X&Y=¬(¬Xv¬Y).

Базисы Система S4={1,&, } образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S1 а затем использовать соотношения: ¬X=1 X XvY=X Y X&Y Система S5={|} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S2 а затем использовать соотношения: X&Y=¬(¬X|¬Y) ¬X=X|X

Базисы Система S6={} образует базис. Произвольную функцию можно сначала привести к виду, содержащему связки из S3 а затем использовать соотношения: XvY=¬(¬X|¬Y) ¬X=XX Система S7={,0} образует базис.