Логика высказываний и предикатов основные понятия
Обновлено: 21.11.2024
Информатика , как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур.
Алгеброй A называется некоторая совокупность определенных элементов X , с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.
Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции ).
Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры .
Утверждение ( высказывательная форма ) – основная единица , неделимая с точки зрения отражения смысла информации (семантики).
Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь" , " true " и "fаlse" или "1" и "0".
Переменная , значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.
Пример. Рассмотрим словосочетания:
- Москва – столица США.
- Житель города Москва.
- 5 – 7 + 8 .
- 5 – 9 + 28 = 4 .
- В пятую неделю зимы было очень холодно.
- В Антарктиде живут тигры.
Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).
Пример. Не является высказыванием и "парадокс лжеца" (Эвбулид, учитель Демосфена, около 350 лет до н.э.): "То, что я сейчас утверждаю, – ложно", ибо если оно истинно – то оно ложно, а если допустить, что оно ложно, то оно истинно. Это неопределенная высказывательная форма . Аналогичный пример принадлежит известному математику, логику Гёделю (1931 г.): "То, что утверждается в этом предложении, не может быть доказано". Если его можно опровергнуть, то его нельзя доказать, а если его нельзя опровергнуть, то его можно доказать. Предложения такого рода не могут быть доказаны или опровергнуты в пределах того языка (той теории, алгебры ), с помощью которой они сформулированы. Известны многие подобные парадоксы.
Рассматривая высказывания , мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их.
Пример. Построим из ниже заданных простых высказываний составные, сложные высказывания , принимающие значение "истина" , "ложь" :
- "Зима – холодное время года".
- "Пальто – теплая одежда".
- "Камин – источник тепла".
Истинным будет, например, сложное высказывание : "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание : "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры.
Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью.
Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависят хотя бы от двух простых.
Пример. Выражение "х = у" – предикат , "х > 5" – предикат , а "7 > 5" – высказывание . Утверждение "Хорошо" не является высказыванием , утверждение "Оценка студента А по информатике – хорошая" – простое высказывание , утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание , состоящее из двух простых.
Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = .
Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели" . Найдем множество истинности предикатов р и q , если " />
, " />
. Получаем, что " />
, " />
.
Множество логических переменных с определенными над ним операциями: " />
– отрицания или инверсии, – логического сложения или дизъюнкции, – логического умножения или конъюнкции называется алгеброй предикатов (и высказываний ) , если эти операции удовлетворяют следующим аксиомам :
Аксиома двойного отрицания:
>=x" />
Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции ):
Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):
Аксиомы одинаковых операндов:
Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):
Аксиомы распределения операции ( дизъюнкции относительно конъюнкции и наоборот):
Аксиомы де Моргана (перенесения бинарной операции на операнды):
= \overline\lor\overline, \overline Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):
)=x, x\lor(y\land\overline)=x" /> Аксиома существования единицы ( истина , true, 1) и нуля ( ложь , false, 0), причем,
=1, \overline=0, \overline\lor x=1, \overline\land x = 0" /> Из этих аксиом следует ряд полезных соотношений, например,
\lor x=1,\\ \overline\land x=0" /> Читайте также: