67605

Булева алгебра, математическая логика, алгебра логики

Лекция

Математика и математический анализ

Каждому двоичному набору можно сопоставить число номер опр расстоянием Хемминга между вершинами и куба называется число опр наборы и называются соседними если и противоположными если все координаты разные.

Русский

2014-09-12

273 KB

1 чел.

Лекция №14 (14.03.00)

Булева алгебра, математическая логика, алгебра логики.

Литература:

1. Яблонский. Введение в дискретную математику. 1986, Москва, Наука

2. Гаврилов, Сапоженко. Задачи и упражнения по курсу дискретной математики.

опр || набор =(1, 2,…, n) где i{0,1}, i=1,…,n называется Булевым (двоичным) набором.

- i - компоненты набора (координаты вектора)

- n – длина набора (размерность).

опр || нормой вектора называют сумму его координат.

опр || множество всех двоичных наборов длины n образуют n-мерный булев (или двоичный) куб . Наборы  называют вершинами куба .

Каждому двоичному набору  можно сопоставить число (номер)

опр || расстоянием Хемминга между вершинами  и  куба  называется число

опр || наборы  и  называются соседними если  и противоположными если  (все координаты разные).

опр || набор  предшествует (или не больше) набора  (), если i i, i=1,…,n.

Если , , то набор  строго меньше (строго предшествует) набору  ().

опр || наборы  и  называются сравнимыми, если  или .

опр || набор  непосредственно предшествует  если  и

утв || отношение является отношением частичного порядка на множестве .

опр || функция  определенная на множестве  и принимающая значения  из множества {0,1} называется функцией алгебры логики (булевой функцией).

Множество всех булевых функций, зависящих от  будем обозначать .

При n = 0 функция называется ноль местной (const) f=0 или f=1.

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

f

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

1

1

1

1

1

1

1

в которой наборы выписываются в порядке возрастания их номеров.

Имея в виду такое расположение наборов функцию можно задать вектором ее значений

(1, 2,…, k), k=2n.

Элементарные функции

0 и 1 - местные

x

f=0

f=1

f1

f2

0

0

1

0

1

1

0

1

1

0

f=0 - тождественный ноль,

f=1 - тождественная единица,

f1(x)=x – тождественная функция

;; - отрицание x, не x, not x

Двуместные функции

f3

f4

f5

f6

f7

f8

f9

f10

f11

0

0

0

0

0

1

1

1

1

0

1

0

1

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

1

1

1

0

1

1

0

0

1

0

f3 - называется конъюнкция

f4 - дизъюнкция

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

f6 - эквиваленция (когда )

f7 - импликация

из правды правда, из лжи правда/ложь

f8 - штрих Шеффера, (антиконъюнкция, не-и)

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

Символы … называются логическими связками.

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

опр || Если для всех наборов   то переменная xi называется фиктивной переменной.

опр || функции f1 и f2 называются равными, если f1 получается из f2 добавлением или изъятием фиктивных элементов.

Формулы

опр ||Формулой над множеством Ф функциональных символов будем называть всякое (и только такое) выражение вида

1) 0, 1- константы;

2) x-любая переменная из множества X;

3) выражения вида (UB), где U,B – формулы, - символ любой двуместной связки (,,,,,).

4)  - отрицание;

Для сокращения записи формул принимаются следующие соглашения:

а) внешние скобки опускаются;

б) считается, что операция отрицания выполняется в первую очередь;

в) следующей по старшинству считается операция конъюнкции; затем – все остальные.

Примеры:

- не есть формула, так как неправильно стоят скобки,

- не стоят скобки вообще

Сопоставим формуле  функцию

опр || Функцию называют симметричной по переменным , если для подстановки

Основные эквивалентности алгебры логики

Свойства:

1) коммутативность

2) ассоциативность

3) дистрибутивность

 а)

 б)

 в)

4) правила Деморгана

 а)   

 б)  

5) правила поглощения

 а)  

 б)  

6)

 а)

 б)

7

 а)

 б)

 в)

 г)

 д)

8)

 а)

 б)

 в)

9)

 а)

 б)

Примеры

Доказать эквивалентность формул

Двойственные функции

опр || функция  называется двойственной функцией к функции .

Пример.

x1

x2

x3

0

0

0

1

0

0

0

1

1

1

0

1

0

0

0

0

1

1

0

1

1

0

0

0

1

1

0

1

1

1

1

1

0

0

0

1

1

1

1

0

Правило ||

Чтобы получить двойственную функцию нужно инвертировать , а затем перевернуть таблицу.

Соответствие элементарных функций

f    0, 1, x, , x1&, x1

f*  1, 0, x, , x1, x1&

Из определения двойственности следует, что

Теорема || Пусть

 

Тогда

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

Отсюда вытекает принцип двойственности: двойственной к формуле

является формула .

Пусть формула содержит только символы &, , . Тогда для получения  из U нужно заменить:

Из принципа двойственности вытекает, что

.

В частности,

.


 

А также другие работы, которые могут Вас заинтересовать

2840. Генетика как наука и ее теоретические аспекты 256.5 KB
  ЭТАПЫ РАЗВИТИЯ ГЕНЕТИКИ КАК НАУКИ. Генетика – наука о наследственности и изменчивости организмов, о закономерностях наследственной изменчивости и о материальных основах наследственности. а) Развитие классической генетики (создание самой наук...
2841. Генетика пола 116 KB
  Генетика пола Цель: Выявить основные закономерности наследования признаков, сцепленных с полом Задачи: 1. Изучить закономерности наследования признаков, сцепленных с полом, у дрозофилы 2. Изучить закономерности наследования признаков, сцепленных с п...
2842. Функции как совокупность объявлений и операторов 79 KB
  Функции Функция – это совокупность объявлений и операторов, предназначенных для выполнения отдельной задачи и заключённых в специальный блок. Необходимость в использовании функций возникает при решении сложных задач, когда нужно выполнять набор...
2843. Время жизни и область видимости в программировании 54 KB
  Время жизни и область видимости В языке C блоком считается последовательность объявлений, определений и операторов, заключенная в фигурные скобки. Объект языка C может быть объявлен на внешнем уровне (вне любого блока), на внутреннем уровне (внутри ...
2844. Препроцессор языка C 75.5 KB
  Препроцессор языка C Препроцессор языка C – это программа, выполняющая обработку исходного кода для передачи его компилятору, в процессе которой происходит подстановка директив и выполнение операций препроцессора. Все директивы препроцессора на...
2845. Интерпретация составных описателей 36 KB
  Интерпретация составных описателей При объявлении переменных, массивов, указателей или функций кроме простых идентификаторов могут использоваться составные описатели. Составной описатель – это идентификатор, дополненный более чем одним признако...
2846. Типы данных, определяемые пользователем (агрегативные типы данных) 51 KB
  Типы данных, определяемые пользователем (агрегативные типы данных) Язык C позволяет программисту создавать следующие типы данных: переименование типов перечислимый тип структура битовые поля объединение Переименование типов. Язык C позволяет дать но...
2847. Прерывания в ОС MS-DOS 36 KB
  Прерывания в ОС MS-DOS Драйвер – это программа, являющаяся посредником между устройством и программой пользователя и предоставляющая набор функций для работы с устройством. В MS-DOS существуют драйверы символьных устройств (за одну операцию обм...
2848. Процесс взаимодействия системы с клавиатурой в ОС MS-DOS 39 KB
  Процесс взаимодействия системы с клавиатурой в ОС MS-DOS Клавиатура – это устройство компьютера, предназначенное для ввода текстовой информации. Технически клавиатура представляет собой матрицу ключей (кнопок), замыкаемых пользователем при нажа...