Кафедра ЮНЕСКО по НИТ1 5. Лекция: Высказывания и предикаты: Информатика

Кафедра ЮНЕСКО по НИТ 2 Цель: рассмотреть основные понятия; сведения алгебры высказываний и предикатов – высказывания (предикаты, аксиомы, логические выражения и функции, эквивалентные выражения и приведение к эквивалентному выражению); другие сопутствующие понятия и факты логики, а также инфологические задачи.

Кафедра ЮНЕСКО по НИТ 3 Информатика и алгебра Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) системы. Алгебра – наиболее адекватный математический аппарат описания действий в них, поэтому алгебраический аппарат наилучшим образом подходит для описания информационных систем общей природы, отвлеченно от их предметной направленности. Информационные процессы хорошо формализуются с помощью различных алгебраических структур.

Кафедра ЮНЕСКО по НИТ 4 Основные понятия Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f ( часто определяемые по сходству с операциями сложения и умножения чисел ), которые удовлетворяют определенным свойствам – аксиомам алгебры. Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции). Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.

Кафедра ЮНЕСКО по НИТ 5 Основные понятия Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики). Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать, истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0". Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

Кафедра ЮНЕСКО по НИТ 6 Пример. Рассмотрим словосочетания: 1. Москва – столица США. 2. Житель города Москва – – = В пятую неделю зимы было очень холодно. 6. В Антарктиде живут тигры. Высказывание должно быть однозначно истинным или однозначно ложным, поэтому высказываниями являются только утверждения 1), 4), 6).

Кафедра ЮНЕСКО по НИТ 7 Высказывания Рассматривая высказывания, мы не обращаем внимания на их внутреннюю структуру и можем разлагать их на структурные части, равно как и объединять их. Пример. Построим из ниже заданных простых высказываний составные, сложные высказывания, принимающие значение "истина", "ложь": "Зима – холодное время года". "Пальто – теплая одежда". "Камин – источник тепла". Истинным будет, например, сложное высказывание: "Зима – холодное время года и зимой носят пальто", а ложным будет, например, высказывание: "Некоторые ходят в пальто, поэтому на улице зима". Придумайте другие примеры.

Кафедра ЮНЕСКО по НИТ 8 Предикат Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью. Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависит хотя бы от двух простых. Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание. Утверждение "Хорошо" не является высказыванием, утверждение "Оценка студента А по информатике – хорошая" – простое высказывание, утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание, состоящее из двух простых.

Кафедра ЮНЕСКО по НИТ 9 Логическая функция Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Кафедра ЮНЕСКО по НИТ 10 Пример Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинности предикатов р и q, если Получаем, что,

Кафедра ЮНЕСКО по НИТ 11 Алгебра предикатов: Множество логических переменных с определенными над ним операциями: – отрицания или инверсии, – логического сложения или дизъюнкции, – логического умножения или конъюнкции называется алгеброй предикатов (и высказываний), если эти операции удовлетворяют следующим аксиомам: Аксиома двойного отрицания: Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции):

Кафедра ЮНЕСКО по НИТ 12 Аксиомы: Аксиома двойного отрицания: Аксиомы переместительности операндов (относительно операций дизъюнкции и конъюнкции): Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

Кафедра ЮНЕСКО по НИТ 13 Аксиомы Аксиомы одинаковых операндов: Аксиомы поглощения (множителем множителя- суммы или слагаемым слагаемого-произведения): Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):

Кафедра ЮНЕСКО по НИТ 14 Аксиомы Аксиомы де Моргана (перенесения бинарной операции на операнды): Аксиомы нейтральности (взаимноинверсных множителей или слагаемых): Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

Кафедра ЮНЕСКО по НИТ 15 Точность Из этих аксиом следует ряд полезных соотношений, например,

Кафедра ЮНЕСКО по НИТ 16 Базовые операции алгебры Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Булеву функцию n переменных можно полностью определить таблицей из 2n строк. Итак, эти операции определяются совмещенной таблицей (таблицей истинности этой функции) значений вида:

Кафедра ЮНЕСКО по НИТ 17 Пример. Составим таблицу истинности функции. Эта таблица имеет вид Следовательно, функция тождественно-истинна. Это можно было доказать (проверить) и с помощью аксиом:

Кафедра ЮНЕСКО по НИТ 18 Пример : Пример. Заполним таблицу истинности трехместной логической функции. Эта таблица имеет вид

Кафедра ЮНЕСКО по НИТ 19 Пример. Изобразим графически множество истинности двухместного предиката вида р(х,у) = "модуль числа х равен модулю числа у", если задана область изменения аргументов:. Имеем соотношение

Кафедра ЮНЕСКО по НИТ 20 Смысл предикатов р1(х,у) и р2(х,у) очевиден. Множество изображается графиком функции y=|x|, который дан на рисунке: график функции y = |x|

Кафедра ЮНЕСКО по НИТ 21 Небазовые операции Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов (можно их назвать небазовыми операциями): 1. импликации: 2. эквиваленции:

Кафедра ЮНЕСКО по НИТ 22 При выполнении логических операций в компьютере они сводятся к поразрядному сравнению битовых комбинаций. Эти операции достаточно быстро (аппаратно) выполняемы, так как сводятся к выяснению совпадения или несовпадения битов. В логических формулах определено старшинство операций, например: скобки, отрицание, конъюнкция, дизъюнкция (остальные, небазовые операции пока не учитываем). Всегда истинные формулы называют тавтологиями.

Кафедра ЮНЕСКО по НИТ 23 Всегда истинные формулы называют тавтологиями. Логические функции эквивалентны, если совпадают их таблицы истинности, то есть совпадают области определения и значения, а также сами значения функции при одних и тех же наборах переменных из числа всех допустимых значений. Если это совпадение происходит на части множества допустимых значений, то формулы называются эквивалентными лишь на этой части (на этом подмножестве).

Кафедра ЮНЕСКО по НИТ 24 Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь). Пример. Упростим:

Кафедра ЮНЕСКО по НИТ 25 Задача доказательства равенства двух логических выражений (функций) состоит в установлении эквивалентности этих функций на некотором множестве значений всех переменных, входящих в данную функцию. Пример. Докажем равенство логических выражений: Используя аксиомы алгебры предикатов, получаем равенства Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью.

Кафедра ЮНЕСКО по НИТ 26 Такие задачи решаются с помощью аксиом алгебры предикатов одним из следующих способов: правая часть равенства приводится к левой части; левая часть равенства приводится к правой части; обе части равенства приводятся к третьему выражению.

Кафедра ЮНЕСКО по НИТ 27 Информационно-логическая (инфологическая) задача Логические функции позволяет эффективно решать так называемые инфологические (информационно-логические) задачи, доказывать утверждения. Информационно-логическая (инфологическая) задача – это задача, в которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача.

Кафедра ЮНЕСКО по НИТ 28 Рассмотрим пример информационно-логической задачи). Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. В ходе следствия Браун сказал, что преступники были на синем "Бьюике", Джонс сказал, что это был черный "Крайслер", Смит утверждал, что это был "Форд", но не синий. Каждый указал неправильно либо марку, либо цвет автомобиля. Определим истинный цвет и истинную марку автомобиля. Рассмотрим простые высказывания вида: х = "машина – синяя", у = "машина – Бьюик", z = "машина – черная", u = "машина – Крайслер", v = "машина – Форд".

Кафедра ЮНЕСКО по НИТ 29 На их основе высказывание Брауна можно записать в виде сложного логического выражения вида, высказывание Джонса – в виде, а высказывание Смита – в виде. Так как в каждом из этих выражений одна из переменных принимает значение "истина", то истинны и дизъюнкции вида: По определению конъюнкции, Это выражение мы взяли из-за однозначности равенства 1 конъюнкции и неоднозначности (многовариантности) его равенства нулю.

Кафедра ЮНЕСКО по НИТ 30 Упростим выражение: Мы использовали тот факт, что одновременно не могут быть истинными два высказывания относительно цвета или два высказывания относительно марки машины. Так как конъюнкция истинна только тогда, когда то заключаем, что автомобиль был черным "Бьюиком".

Кафедра ЮНЕСКО по НИТ 31 Алгебра логики Чтобы переложить на ЭВМ работы мыслительного характера, эти правила необходимо строго сформулировать, формализовать. Это позволяет осуществить алгебра логики. Приведем некоторые аксиомы логики – науки, изучающей методы доказательства и опровержения утверждений. Аксиома исключения третьего: либо имеет место высказывание, либо его отрицание. Аксиома противоречия: высказывания и его отрицание не могут иметь места одновременно. Аксиома двойного отрицания: двукратное отрицание какого-либо утверждения равносильно исходному утверждению. Аксиома тождества: всякое высказывание тождественно самому себе.

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