Файловый архив студентов. Файловый архив студентов.
1261 вуз, 4606 предмет.
/ Регистрация
FAQ Обратная связь Вопросы и предложения
Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
Предмет:
[НЕСОРТИРОВАННОЕ]
Файл:

pdm_02

.pdf
Скачиваний:
24
Добавлен:
14.04.2015
Размер:
1 Mб
Скачать
☆

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

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

 

 

курс лекций

 

 

 

 

лекция 2

 

 

 

 

 

 

 

Элементы алгебры логики,

 

 

Кафедра

предикаты

 

 

 

 

 

«Проектирования и

 

 

 

безопасности

 

 

 

компьютерных систем»

 

 

Гришенцев А. Ю.

 

 

 

www.moveinfo.ru

 

 

 

 

 

Санкт-Петербург

 

 

 

 

2014

1

 

 

 

Алгебра логики

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

Алгебра логики возникла в середине XIX в. в трудах Дж. Буля и развивалась затем в работах Ч. Пирса, П. С. Порецкого, Б. Рассела, Д. Гильберта и др. Создание алгебры логики было попыткой решать традиционные логические задачи алгебраическими методами.

Скульптура «Мыслитель» (фр. Le Penseur) Огюста Родена, которая часто используется в качестве символа философии. Философия – мать всех наук.

Кроме двузначной логики существует многозначная логика, такая логика в которой допускается более двух истинностных значений для высказываний.

2

Метод математической индукции

Аксиома индукции: если для некоторого утверждения P(x):

1. P(1)

x, P(x)

2. ( n, P(n)) P(n 1) true

Пункт 2 называют индуктивным переходом.

Для доказательства некоторого высказывания методом математической индукции требуется: базис P(1), предположение P(n) и шаг P(n+1).

Математическая индукция – следование в рассуждениях от частного к общему.

Математическая дедукция – следование в рассуждениях от общего к частному.

Вопрос: каким методом пользовался Шерлок Холмс?

3

Функции алгебры логики

Пусть двухэлементное множество E2 ={0,1}, тогда набор длины n из 0 и 1 есть последовательность длины n, составленная из 0 и 1.

Пример:

(0); (1) – наборы длины 1;

(0,0); (0,1); (1,0); (1,1) – наборы длины 2; и т.д.

Теорема.

Пусть E n есть множество всех наборов длины n,

 

 

 

 

 

2

 

тогда число всех наборов h(n) из

E2n равно 2n.

 

Доказательство методом математической индукции.

 

Базис : n =1, h(n) = 2.

 

 

Предположение : h(n) = 2n. Шаг : h(n +1) = 2n+1.

 

Доказательство :

 

 

 

E n+1

= 2

 

E n

→ (n +1), h(n +1) = 2

h(n) →

 

2

 

 

 

2

 

 

→ h(n +1) = 2n + 2n = 2n+1, ч.т.д.

 

4

Функции алгебры логики

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

Высказывание не содержащее связок (операторов) называется простым (константным), содержащее связки - сложным.

Будем ставить в соответствие истинности (true) 1, а значению лжи (false) 0.

true 1

(2.1)

false 0

n местная функция f

есть отображение f : En

E .

 

 

 

2

2

Теорема. Число всех n

местных функций алгебры логики

 

 

 

 

 

равно 2(2n ). Множество всех функций от n переменных обозначим Pn , тогда | Pn | 2(2n ).

Теорема легко доказывается используя таблицу истинности, для n аргументов число строк в таблице равно 2n следовательно, число функций 2↑(2n).

Следует отметить, что в вычислительных системах истиной

5

считается любое значение отличное от нуля.

Операторы алгебры логики

Оператор

Название

Эквив. Обозн.

Тип

Базис

 

 

 

 

 

 

 

 

 

 

 

 

x

 

отрицание, не

!x,

~

 

 

x

унарная

 

 

x,

 

 

 

x

y

дизъюнкция, или,

x

y,

x ||

y

бинарная

 

логическое сложение

да

 

 

 

 

 

 

 

 

 

 

x

y

конъюнкция, и,

xy, x

y,

 

x & y

бинарная

 

логическое умножение

 

 

 

 

 

 

 

 

 

 

 

 

 

x

y

импликация, следствие

x

 

y

 

 

бинарная

нет

 

 

 

 

 

 

 

 

 

 

 

 

x

y

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

x

y,

 

x

y

бинарная

нет

равносильность

 

 

 

 

 

 

 

 

 

 

 

 

x | y

штрих Шеффера,

 

 

 

 

 

 

 

 

 

x

y,

 

x

y

бинарная

да

и не

 

 

 

 

 

 

 

 

 

 

 

 

x

y

стрелка Пирса,

 

 

 

 

 

 

 

 

 

 

x

 

y

 

 

бинарная

да

или не

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

y

сложение по модулю

 

 

 

 

 

 

 

 

 

два,

 

x

2 y

 

 

бинарная

нет

 

 

 

 

 

 

 

исключающее или

 

 

 

 

 

 

 

 

 

В специальной литературе можно встретить большое многообразие

 

 

 

обозначений операторов булевой алгебры.

 

 

Будем преимущественно использовать обозначения содержащиеся в

6

 

 

столбце «Оператор».

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблицы истинности

Таблица истинности -

способ задания и определения функции алгебры

логики.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

y

x

x y

x y x

y

x

 

y

x | y x

y

x

y

const.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

0

1

0

0

1

 

1

 

1

1

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

1

1

0

1

 

0

 

1

0

 

1

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

0

1

0

0

 

0

 

1

0

 

1

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

1

0

1

1

1

 

1

 

0

0

 

0

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Существуют таблицы истинности другого вида, например, карты Карно являются одним из видов таблиц истинности.

Функцию алгебры логики возможно задать: -таблично, при помощи таблицы истинности;

-аналитически, при помощи формального выражения;

-графически, например, при помощи диаграммы или бинарного графа.

7

Взаимные преобразования с помощью таблиц истинности

Пример (2.2). Выразить

функцию

f (x, y) x y, через

 

 

 

оператор образующий базис

стрелку Пирса.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

задано

I.I

I.I

 

II

результат

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

y

x↓y

x↓x

y↓y

(x↓x) ↓(y↓y)

(x↓y)↓[(x↓x) ↓(y↓y)]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

0

1

1

1

 

0

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

1

0

1

0

 

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

0

0

0

1

 

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

1

0

0

0

 

1

0

 

 

 

 

 

 

 

 

 

 

 

 

 

Применение таблиц истинности позволяет сделать процесс преобразования более наглядным.

8

Равносильные формулы

Одна функция может иметь множество реализаций. Формулы, реализующие одну и ту же функцию, называют равносильными.

свойства констант: 1

x

x,

0

x

0, 1

x

1,

0 x

x

противоречие :

 

x

x

0

 

 

 

 

 

 

 

 

 

 

 

исключение третьего :

x

x

1

 

 

 

 

 

 

 

 

 

 

коммутативность :

x

y

y

x, x

y

y

x

 

 

 

 

 

ассоциативность :

x

( y

z)

 

( y

x)

z,

x

( y

z)

( y x) z

дистрибутивность:

x

( y

z)

 

(x

y)

(x

z),

 

 

 

 

x ( y z)

 

(x y) (x z)

 

 

 

идемпотентность :

x

x

x,

x

x

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

двойное отрицание:

 

x

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

законы де Моргана: (x

y)

 

(x

y),

(x

y)

(x

y)

 

контрапозиция :

 

x

y

y

x

 

 

 

 

 

 

 

 

поглощение:

 

x

(x

y)

x, x (x

y)

x

 

 

 

Проверку и доказательство равносильности формул возможно произвести

 

при помощи таблиц истинности.

9

Предполные классы функций алгебры логики

Теорема. Классы функций T0, T1, T*, TM, TL замкнуты.

Класс функций, сохраняющих 0 :

T0 = { f | f (0,0,...,0) = 0}.

Класс функций, сохраняющих 1:

T1 = { f | f (1,1,...,1) =1}.

Класс самодвойственных функций:

T* = { f | f (x1, x2 ,..., xn ) = f (x1, x2 ,..., xn )}.

Класс монотонных функций:

TM = { f | i(ai ≤ bi ) → f (a1, a2 ,..., an ) ≤ f (b1, b2 ,..., bn )}

Класс линейных функций:

TL = { f | f (x1, x2 ,..., xn ) = a0 a1x1 ... an xn , ai E2}

Классы T0, T1, T*, TM, TL называют предполными классами объединения функций этого класса с любой функцией, не принадлежащей ему, порождает все множество Pn.

10

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
Помощь Обратная связь Вопросы и предложения Пользовательское соглашение Политика конфиденциальности