![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Лекция: Высказывания и предикаты
ЧАСТЬ 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 переменных можно полностью определить таблицей из Итак, эти операции определяются совмещенной таблицей значений вида
Такая таблица всех значений некоторой логической функции называется таблицей истинности этой функции. Пример. Составим таблицу истинности функции
Следовательно, функция тождественно-истинна. Это можно было доказать (проверить) и с помощью аксиом:
Дата добавления: 2014-01-05; Просмотров: 1121; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |