Лекция: Высказывания и предикаты

ЧАСТЬ 1. ВВЕДЕНИЕ

Редактор

Компьютерная верстка А.В. Кибардина

ИД N 06263 от 12.11.2001 г.

__________________________________________________________

Подписано в печать Формат 60х84 1/16

Бумага типографская Офсетная печать Усл. печ.л.

Уч.-изд.л. Тираж Заказ Цена“С”

__________________________________________________________

Редакционно-издательский отдел ГОУ УГТУ−УПИ

620002, Екатеринбург, ул.Мира, 19

Ризография НИЧ ГОУ ВПО УГТУ-УПИ

620002, Екатеринбург, ул.Мира, 19

Информатика, как было рассмотрено выше, изучает знаковые (алфавитные) системы.

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

Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.

Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).

Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.

Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".

Переменная, значениями которой могут быть лишь значения "1" или "0", называется логической переменной или булевой переменной.

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

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

Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание. Утверждение "Хорошо" не является высказыванием, утверждение "Оценка студента А по информатике – хорошая" – простое высказывание, утверждение "Вчера была ясная погода, я был вчера на рыбалке" – сложное высказывание, состоящее из двух простых.

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

Множество логических переменных с определенными над ним операциями: – отрицания или инверсии, – логического сложения или дизъюнкции, – логического умножения или конъюнкции называется алгеброй предикатов (и высказываний), если эти операции удовлетворяют следующим аксиомам:

1. Аксиома двойного отрицания:

2. Аксиомы переместительности операндов (относительно операций дизъюнкции и

конъюнкции):

3. Аксиомы переместительности операций дизъюнкции и конъюнкции (относительно операндов):

4. Аксиомы одинаковых операндов:

5. Аксиомы поглощения (множителем — множителя-суммы или слагаемым — слагаемого-произведения):

6. Аксиомы распределения операции (дизъюнкции относительно конъюнкции и наоборот):

7. Аксиомы де Моргана (перенесения бинарной операции на операнды):

,

8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых):

,

9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

Из этих аксиом следует ряд полезных соотношений, например,

.

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

Итак, эти операции определяются совмещенной таблицей значений вида

X	y

Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции.

Пример. Составим таблицу истинности функции . Эта таблица имеет вид

X	y			z

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

Дата добавления: 2014-01-05