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 нужно заменить:

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

.

В частности,

.


 

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

36622. Трудова поведінка: зміст, структура, функції 92.5 KB
  Трудова поведінка як різновид соціальної поведінки. Зміст структура та функції трудової поведінки. Види трудової поведінки. Механізми регуляції трудової поведінки.
36623. Информационные системы предприятия 1.03 MB
  В самом общем виде под информационной системой предприятия (ИСП) понимается весь комплекс данных и знаний, используемых на предприятии в целях управления и любой другой, направленной на экономический эффект деятельности, вместе со средствами получения, учета, хранения, доступа, представления, а также анализа данных и знаний.
36624. Ринок цінних паперів та його місто в системі фінансових ринків 2 MB
  Ринок цінних паперів та його місто в системі фінансових ринків Змістовий модуль 1. Поняття та види ринків цінних паперів 1. Ринок цінних паперів в системі фінансових ринків та його види. Основні види ринків цінних паперів.
36625. Cовершенствование организации и технологии технического обслуживания и текущего ремонта автомобилей 909.5 KB
  Проблема технического обслуживания, текущего ремонта и диагностики в участка, имеющая недостатки как в организации, так и в выполнении плана ТО является актуальной и требующая пересмотра существующей организации техобслуживания и диагностики.
36626. Безопасность жизнедеятельности. Конспект лекций 1.77 MB
  В конспекте использован материал новых Межотраслевых правил по охране труда. Условия труда. Метеорологические условия труда и чистота воздуха. Управление охраной труда.
36627. ПРОГРАММИРОВАНИЕ. Курс лекций 1.11 MB
  Понятия объекта класса объектов. Доступность компонентов класса. Статические и константные компоненты класса. Указатели на компоненты класса.
36628. ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ВЫСОКОГО УРОВНЯ 1015 KB
  1 Языки программирования Языки программирования делятся на 3 основных класса как показано на рис.3 Понятие алгоритма и его свойства Алгоритм это точное предписание о выполнении в определенном порядке некоторых операций приводящих к решению всех задач данного класса. Непосредственный предшественник C язык Си с классами появился в 1979 году а в 1997 году был принят международный стандарт C который фактически подвел итоги его 20летнего развития. Если мы говорим об объектноориентированной программе то она должна создать объект...
36629. РЕИНЖИНИРИНГ БИЗНЕС-ПРОЦЕССОВ 2.09 MB
  При выстраивании системы управления и взаимодействия в одном процессе непременно придется захватить взаимодействие данного пилотного процесса с другими. Появление эффекта перетягивания одеяла когда руководитель пилотного процесса добивается регламентации и последующего выполнения совместных работ с точки зрения выгоды и преимуществ своего процесса а не всей организации. Воспользовавшись правом преимущественного создания регламентирующих документов владелец пилотного процесса может создать себе более льготные условия по обеспечению...
36630. Наплавка зуба ковша 2.5 MB
  Основным способом соединение деталей является дуговая электрическая сварка. Возможно что, совершенствование существующих способов сварки и резки металлов и их синтез дадут новый способ сварки в твердой фазе