Предикаты и алгебра логики (тема 04)

1. Основы информатики © Казиев В.М. [email protected] Тема 4. Предикаты и алгебра логики

2.

Алгебраический аппарат наилучшим образом подходит для описания
информационных систем общей природы. Информационные процессы
хорошо формализуются с помощью различных алгебраических структур.
Алгеброй A называется некоторая совокупность определенных элементов X, с
заданными над ними определенными операциями f (часто определяемые по
сходству с операциями сложения и умножения чисел), которые
удовлетворяют определенным свойствам – аксиомам алгебры.
Операция f называется n–местной, если связывает n операндов (объектов –
участников этой операции). Совокупность операций алгебры A называется ее
сигнатурой, а совокупность элементов алгебры – носителем алгебры.
Утверждение (высказывательная форма) – основная единица, неделимая с
точки зрения отражения смысла информации (семантики).
Высказывание – некоторое повествовательное утверждение, про которое
можно однозначно сказать («сразу посмотрев на него»), истинно оно или
ложно. Эти два значения всевозможных высказываний обозначаются
«истина» и «ложь», «true» и «fаlse» или «1» и «0».
Переменная, значениями которой могут быть лишь значения «1» или «0»
называется логической переменной или булевой переменной.

3.

Пример. Рассмотрим словосочетания:
Москва – столица США.
Житель города Москва.
5 – 7 + 8.
5 – 9 + 28 = 4.
В пятую неделю зимы было очень холодно.
В Антарктиде живут тигры.
Высказывание должно быть однозначно истинным или однозначно ложным,
поэтому высказываниями являются только утверждения 1),4),6).
Пример. Не является высказыванием и «парадокс лжеца» (Эвбулид, 350 лет
до н.э.): «То, что я сейчас утверждаю, – ложно». Если оно истинно – то
ложно, а если ложно, то - истинно. Это неопределённая высказывательная
форма. Аналогичный пример принадлежит известному математику, логику
Гёделю (1931 г.): «То, что утверждается в этом предложении, не может
быть доказано». Если его можно доказать, то его нельзя доказать, а если его
можно опровергнуть, то его можно доказать.
Известны многие такие парадоксы.

4.

Рассматривая высказывания, не обращаем внимания на их внутреннюю
структуру, разлагая их на структурные части, равно как и объединяя.
Пример. Построим из ниже заданных простых высказываний составные,
сложные высказывания принимающие значение «истина», «ложь»:
1) «Зима – холодное время года».
2) «Пальто – теплая одежда».
3) «Камин – источник тепла».
Истинным будет, например, сложное высказывание: «Зима – холодное время
года и зимой носят пальто», а ложным будет, например, высказывание:
«Некоторые ходят в пальто, поэтому на улице зима».
Предикат – высказывательная форма с логическими переменными
(множество значений этих переменных вполне определено), имеющая смысл
при любых допустимых значениях этих переменных. Количество этих
переменных в записи предиката называется его местностью.
Простые высказывания или предикаты не зависят от других высказываний
или предикатов («не разбиваемы на более простые»), а сложные – зависит
хотя бы от двух простых.

5.

Пример. Выражение «х=у» – предикат, «х>5» – предикат, а «7>5» –
высказывание. Утверждение «Хорошо» не является высказыванием,
утверждение «Оценка студента А по информатике – хорошая» – простое
высказывание, утверждение «Вчера была ясная погода, я был вчера на
рыбалке» – сложное высказывание, состоящее из двух простых.
Логической (булевой) функцией f(х) называется некоторая функциональная
зависимость, в которой аргумент х – логическая переменная с заданным
множеством изменений аргумента, а значения функции f(x) берутся из
двухэлементного множества R(f)={1,0}.
Пример. Заданы предикаты вида р = «число х делится нацело на 3» и q = «у –
день недели». Найдём множество истинности предикатов р и q, если
х {1,4,6,16,20,24}, у {первый, вторник, среда, 1999, зима, выходной,
праздник, воскресенье}. Получаем, что D(р)={6, 24}, D(q)={вторник, среда,
воскресенье}.

6.

6

7.

8.

x
y
0
x
0
0
y
1
1
0
0
1
1
0
1
0
0
1
0
1
1
0
1
1

9.

В логических формулах определено старшинство операций, например:
скобки, отрицание, конъюнкция, дизъюнкция (остальные, не базовые
операции пока не учитываем).
Всегда истинные формулы называют тавтологиями.
Логические функции эквивалентны, если совпадают их таблицы
истинности, то есть совпадают области определения и значения, а также сами
значения функции при одних и тех же наборах переменных из числа всех
допустимых значений. Если это совпадение происходит на части множества
допустимых значений, то формулы называются эквивалентными лишь на
этой части (на этом подмножестве).
Задача упрощения логического выражения состоит в преобразовании его к
более простому (по числу переменных, операций или операндов)
эквивалентному выражению. Наиболее простой вид получается при сведении
функции к постоянной – 1 (истина) или 0 (ложь).

10.

Задача доказательства равенства двух логических выражений
(функций) состоит в установлении эквивалентности этих функций на
некотором множестве значений всех переменных, входящих в данную
функцию. Такие задачи решаются с помощью аксиом алгебры
предикатов одним из следующих способов:
• правая часть равенства приводится к левой части;
• левая часть равенства приводится к правой части;
• обе части равенства приводятся к третьему выражению.
Логические функции позволяет эффективно решать инфологические
(информационно-логические) задачи, доказывать утверждения.
Информационно–логическая (инфологическая) задача – это задача, в
которой необходимо установить некоторые информационные или
логические связи и сделать необходимые причинно-следственные
инфологические выводы. Информационно–логические задачи решают с
помощью алгебры предикатов.

11.

Законы алгебры высказываний и предикатов сходны с правилами, по
которым человек делает умозаключения, доказывает, мыслит.
Пример. Операции конъюнкции, дизъюнкции, отрицания алгебры
высказываний – аналоги союзов «и», «или», приставки «не»,
используемых при выражении мысли человеком. Чтобы переложить на
ЭВМ работы мыслительного характера, эти правила необходимо строго
сформулировать, формализовать. Это позволяет алгебра логики.
Приведём некоторые аксиомы логики – науки, изучающей методы
доказательства и опровержения утверждений.
Аксиома исключения третьего: либо имеет место высказывание, либо
его отрицание.
Аксиома противоречия: высказывания и его отрицание не могут иметь
места одновременно.
Аксиома двойного отрицания: двукратное отрицание какого-либо
утверждения равносильно исходному утверждению.
Аксиома тождества: всякое высказывание тождественно самому себе.

12.

Если высказывания x и y связаны друг с другом отношением x y, то
говорят, что высказывание y следует из высказывания x (или y –
следствие x); если множество истинности Х высказывания х содержит
множество истинности Y высказывания y, то высказывание x – условие,
высказывание y – заключение, а само соотношение x y – вывод.
Доказательство формальных математических утверждений (теорем) –
последовательность корректных выводов, ведущих от условия к
заключению. Алгебра логики помогает доказывать теоремы (даёт общие
подходы, методы к доказательству).
Общий подход к доказательству теорем методом от противного,
обратных и противоположных теорем можно формализовать с помощью
алгебры логики.

13.

Логические операции в компьютере сводятся к поразрядному сравнению
битовых комбинаций, аппаратно выполняемы. Компьютер, её электронный
логический блок состоит из сотен тысяч вентилей (базовых логических схем),
объединяемых по аксиомам алгебры предикатов в схемы, модули.
Логический вентиль - атом электронных узлов компьютеров. Он работает по
принципу крана (отсюда и название), открывая или закрывая путь сигналам и
предназначен для реализации функций алгебры логики с помощью трех
базовых вентилей (переключательных схем, полупроводниковых схем).
Логические функции отрицания, дизъюнкции и конъюнкции реализуют
логические схемы, называемые инвертором, дизъюнктором и конъюнктором.
Логическая функция «инверсия» или отрицание, реализуется логической
схемой (вентилем), называемой инвертор. Принцип его работы условно
опишем: если, например, “0” или “ложь” отождествить с тем, что на вход
этого устройства скачкообразно поступило напряжение в 0 вольт, то на
выходе получается 1 или “истина”, которую можно также отождествить с
тем, что на выходе снимается напряжение в 1 вольт. Аналогично, при входе
инвертора в 1 вольт (“истина”), на выходе будет сниматься 0 вольт («ложь»).
13

14.

14

15.

Решение задач
1. Составить таблицу истинности функции z x ( x y )
Решение:
x
у
z
x
x ( x y)
x y
0
0
1
1
0
1
0
1
1
1
0
0
0
1
0
0
0
0
0
0
1
1
1
1
Функция – тождественно-истинная. Это доказывается и аксиомами:
z x ( x y) x x y x x y 1 y 1
2. Найти множество истинности двухместного предиката вида р(х,у)=«модуль
числа х равен модулю числа у», если задана область изменения аргументов:
х,у [0;1].
.
Решение: Имеем соотношение: E(p)={(x,y):|x|=|y|}={(x,y):(x=y) (x= –y)}=
={(x,y):x=y} {(x,y):x=–y}=E(p1) E(p2).
15

16.

16