Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
Он перенес на логику законы и правила математических действий, ввел логические операции, предложил способ записи высказываний в символической форме. В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра - алгебра логики (алгебра высказываний). Алгебра логики (алгебра высказываний) - раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике.Суперпозиция двоичных функций может быть записана как формула, которую называют логической формулой. Для реализации преобразователя f примера выше необходимо иметь элементы, реализующие отрицание, дизъюнкцию, конъюнкцию и сложение по модулю два (см. рис. Суперпозицией нескольких простых булевых функций можно построить более сложную функцию, в частности, булеву функцию от большего числа переменных. Поставим вопрос: можно ли суперпозицией фиксированного набора функций представить любую булеву функцию от любого числа переменных? Таблицы истинности также называются интерпретациями логических операций и составляют семантику формул (т. е. придание смысла формулам) в отличие от синтаксиса формул (т. е. формальных законов их построения, данных в определении формулы).Теперь будем рассматривать функции F(x1, x2,…, xn), где xi - логические переменные, которые принимают значения нуля или единицы. Логической функцией F от набора логических переменных х1,…, xn называется функция, которая может принимать только два значения: логический 0 и логическая 1. 3 представлены в упорядоченном виде наборы аргументов для ряда функций - отрицания 0, функций одного, двух и трех аргументов. Система булевых функций {f1, f2,…, fm} называется полной, если любая булева функция может быть выражена через функции f1, f2,…, fm с помощью суперпозиций. Функция f называется элементарной суперпозицией (суперпозицией ранга 1) функций f1, f2,…, fm, если f может быть получена одним из следующих способов: а) переименованием некоторой переменной xj какой-нибудь функции fi;Ранее мы рассматривали ситуации, когда на множество аргументов или логических переменных x1, x2,…, xn не накладывались ограничения, или, что то же самое, функции были определены на всем наборе аргументов.К настоящему времени мы знакомы с двумя формами представления булевых функций: таблица истинности и формула (аналитическая запись).Семантическое дерево - это двоичное дерево, корень которого помечен двоичной функцией от m переменных, из каждого узла идут по два ребра, соответствующих двум значениям очередной переменной, а 2m листьев помечены соответствующими значениями функции. Если на каждом уровне БДР все вершины имеют одну и ту же метку (одинаковые переменные), то такая БДР называется упорядоченной (в англоязычной литературе такое представление называется Ordinary Binary Decision Diagrams, или сокращенно OBDD). 4 показаны все четыре формы представления функции . Сложность представления функции с помощью УБДР существенно зависит от порядка переменных. Интересной проблемой теоретической информатики является нахождение алгоритма, дающего оптимальный порядок переменных булевой функции с точки зрения представления этой функции упорядоченной БДР.Анализ автоматов - нахождение по заданному в том или ином виде автомату отображения «вход-выход», осуществляемого этим автоматом; часто такое отображение можно интерпретировать как вычисление предиката, и поскольку каждый предикат характеризуется своим множеством истинности, то задача анализа автомата сводится к нахождению этого множества (говорят, что это множество распознается автоматом). Далеко не всегда по заданным автомату и множеству удается определить, распознает ли автомат в точности это множество. Трудности синтеза автоматов зависят в основном от того, как заданы условия функционирования автомата. Поэтому для ряда классов автоматов, в частности, для конечных автоматов, разрабатываются специальные языки, с помощью которых удобно задавать условия функционирования автоматов, для которых существуют методы синтеза (регулярные события и выражения, логический язык для задания автоматов). Существуют некоторые классы таких автоматов: автоматы без памяти (комбинационные) автоматы с памятью (последовательностные).
План
Содержание
Часть 3. Элементы алгебры логики 3
3.1 Введение в алгебру логики 3
3.2 Основные функции алгебры логики 5
3.3 Формулы алгебры логики 9
Контрольные вопросы 12
3.4 Законы алгебры логики и следствия из них 12
Контрольные вопросы 16
3.5 Логические функции многих переменных 16
3.6 Построение формул алгебры логики по заданной таблице истинности 18
Контрольные вопросы и упражнения 26
3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса 26
Контрольные вопросы и упражнения 34
3.8 Методы минимизации логических функций 34
Контрольные вопросы 39
3.9 Неполностью определенные логические функции 40
3.10 Формы представления булевых функций 41
3.10.1 Семантические деревья 42
3.10.2 Бинарные диаграммы решений (БДР) 45
3.11 Построение логических схем 45
Контрольные вопросы 45
3.12 Логические конечные автоматы 46
3.12.1 Процессы 50
3.12.2 Конечные автоматы 52
Контрольные вопросы 55
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 60
Часть 3. Элементы алгебры логики
Введение
Алгебру логики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебра логики начала формироваться в 19 веке в трудах английского математика Дж. Буля.
Прежде всего, благодаря труду английского логика Джорджа Буля «Математический анализ логики», был достигнут подлинный прогресс науки, называемый математической логикой. Он перенес на логику законы и правила математических действий, ввел логические операции, предложил способ записи высказываний в символической форме.
В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра - алгебра логики (алгебра высказываний).
Алгебра логики (алгебра высказываний) - раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.
Джордж Буль (1815-1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил только начальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль - профессор математики в Куинс - колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона. Он считается несомненным создателем современной символической (математической) логики.
Огастес де Морган (1806-1871) родился в Индии в семье полковника английских войск. Получил образование в Кембриджском университете. Был профессором математики Лондонского университета. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике. Сам он стремился сблизить обе науки, и его главной заслугой явилось построение логики по образу и подобию математических наук. Независимо от Дж. Буля он открыл основные идеи алгебры логики.
«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.
Высказывание - это имеющее смысл языковое выражение (повествовательное предложение), относительно которого в данной ситуации можно утверждать, что оно либо истинно, либо ложно, т. е. каждому высказыванию можно приписать истинное значение И (истина) или Л (ложь), но не то и другое одновременно.
Примеры: 1. НГТУ - крупнейший «вуз Новосибирска».
2. «Снег зеленый».
3. Р= «Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее ПО».
4. Крокодилы летают очень низко.
«А ты любишь информатику?» - это предложение не является высказыванием.
Уравнение 2 х=4 не является высказыванием. Однако, всякий раз, придавая переменной х определенное числовое значение, будем получать высказывание. Используя частицу «не», а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…» и т. п., можно из одних высказываний строить другие высказывания.
Изучением высказываний занимается Булева алгебра, в которой предполагается, что уже имеется некоторый запас высказываний, для каждого из которых известно истинно оно или ложно. Такие высказывания называют элементарными высказываниями. Из элементарных высказываний могут быть построены сложные с помощью операций алгебры логики.
Знаки логических операций называют логическими связками (или просто связками). Логические связки могут быть одноместные (унарные), двухместные (бинарные), трехместные (тернарные) и т. д.
В алгебре логики логические операции чаще всего описываются при помощи таблиц истинности, содержащих все наборы значений переменных и значения функции этих наборов. Алгебра логики не занимается обоснованием того, почему тому или иному элементарному высказыванию приписано значение истины или лжи. Этот вопрос решается за пределами алгебры логики.
Например: сумма углов в треугольнике - 180 градусов. Алгебра логики отвлекается и от смысловой содержательности высказывания. Она интересуется только одним свойством сложных высказываний: быть истинным (True - 1) или ложным (False - 0).
Список литературы
Акимов В.А. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003, 376 с.
Стол Роберт Р. Множества. Логика. Аксиоматические теории. Пер. с англ. Ю.А. Гастева И.Х. Шмаина. Под ред. Ю.А. Шихановича. М., «Просвещение», 1968, 232 с.
Ершов Ю.А., Полюнин Е.А. Математическая логика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. - мат. лит., 1987, 336 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Высшая школа, 2003, 256 с.
Р. Хаггарти Дискретная математика для программистов Москва: Техносфера, 2003, 320 с.
Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. - М.: ФОРУМ: ИНФРА-М, 2004, 128 с.
7. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. - М.: ИНФРА - М; Новосибирск: НГТУ, 2003, 280 с. - (Серия «Высшее образование»)
8. Новиков Ф.А. Дискретная математика для программистов. - СПБ: Питер, 2001, 304 с.: ил.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
