Дискретная математика (85576)

Посмотреть архив целиком

Министерство образования и науки

Российской Федерации

Российский химико-технологический университет

им. Д.И. Менделеева

Новомосковский институт

Издательский центр


T.П. Тюрина, В.И. Емельянов









Дискретная математика

(часть 3)


Учебное пособие










Новомосковск 2004


Содержание


Часть 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. Элементы алгебры логики


3.1 Введение в алгебру логики


Алгебру логики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебра логики начала формироваться в 19 веке в трудах английского математика Дж. Буля.

Прежде всего, благодаря труду английского логика Джорджа Буля «Математический анализ логики», был достигнут подлинный прогресс науки, называемый математической логикой. Он перенёс на логику законы и правила математических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра – алгебра логики (алгебра высказываний).

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

Джордж Буль (1815–1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил только начальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль – профессор математики в Куинс – колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона. Он считается несомненным создателем современной символической (математической) логики.

Огастес де Морган (1806–1871) родился в Индии в семье полковника английских войск. Получил образование в Кембриджском университете. Был профессором математики Лондонского университета. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике. Сам он стремился сблизить обе науки, и его главной заслугой явилось построение логики по образу и подобию математических наук. Независимо от Дж. Буля он открыл основные идеи алгебры логики.

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.

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

Примеры:

  1. НГТУ – крупнейший «вуз Новосибирска».

  2. «Снег зелёный».

  3. Р= «Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее ПО».

  4. Крокодилы летают очень низко.

«А ты любишь информатику?» – это предложение не является высказыванием.

Уравнение 2+х=4 не является высказыванием. Однако, всякий раз, придавая переменной х определенное числовое значение, будем получать высказывание. Используя частицу «не», а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…» и т. п., можно из одних высказываний строить другие высказывания.

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

Знаки логических операций называют логическими связками (или просто связками). Логические связки могут быть одноместные (унарные), двухместные (бинарные), трехместные (тернарные) и т. д.

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

Например: сумма углов в треугольнике – 180 градусов. Алгебра логики отвлекается и от смысловой содержательности высказывания. Она интересуется только одним свойством сложных высказываний: быть истинным (True – 1) или ложным (False – 0).


3.2 Основные функции алгебры логики


Основной задачей теории булевых функций является разработка систематического метода построения сложных функций из более простых. Этот метод основан на изучении свойств булевых функций.

Основными символами алгебры высказываний являются:

а) пропозиционные переменные Р1, Р2, Р3, …;

б) одноместная связка – () и двуместные связки  (и),  (или), , , ;

в) скобки ().

Переменная, значениями которой являются высказывания, называется пропозиционной переменной.

Пусть А, В-некоторые элементарные высказывания.

Определим новое высказывание Ā (т. е. не А), будем называть его отрицанием (инверсия: , Ā), представим таблицы значений функции отрицания:


А

Ā

1

0

0

1

Рассмотрим наборы истинных значений элементарных функций на наборах аргументов:


A

B

0

0

1

1

0

1

0

1

Таблица 1

Обозначение операции

Другие обозначения

Набор истинных значений

Название логической опции и связки

Как читается

Арифметическая модель

12

АВ

А+В

Max (А, В)

0

1

1

1

Дизъюнкция, логическое сложение, «или»

А или В

A+B-AB

23

АВ

А&В

АВ

Min (А, В)

0

0

0

1

Конъюнкция, логическое умножение «и»

А и В

AB

34

АВ

АВ

АВ

1

1

0

1

Импликация, логическое следование

Если А, то В

А влечет В

1‑A+ AB

45

АВ

АВ

АВ

АВ

1

0

0

1

Эквиваленция, эквивалентность

А тогда и только тогда, когда В; А эквивалентно В

1 – (A-B)2

56

АВ

А+В

АВ

АВ

0

1

1

0

Сумма по модулю 2, сумма Жегалкина

А плюс В; Либо А, либо В


67

АВ


1

1

1

0

Штрих Шеффера, антиконъюнкция

Неверно, что А и В; А штрих Шеффера В


78

АВ

АВ

АВ

1

0

0

0

Стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера

Ни А, ни В; А стрелка Пирса В



Несмотря на то, что булевых функций от любого заданного числа m двоичных переменных конечное число, их слишком много, чтобы иметь запас преобразователей для любых встретившихся отображений. Рассмотрим сначала все возможные функции от одной двоичной переменной. Их четыре, две из них – константы (0 и 1), одна – тождественная функция и только одна – функция отрицания (функция НЕ) – является нетривиальной.


Случайные файлы

Файл
kursovik.doc
82833.rtf
6408-1.rtf
42543.rtf
185553.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.