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

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

.

В частности,

.


 

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

68250. ЕКОНОМІКО-ОРГАНІЗАЦІЙНІ АСПЕКТИ ЕФЕКТИВНОГО ФУНКЦІОНУВАННЯ КАРТОПЛЯРСТВА В АГРОФОРМУВАННЯХ ПОДІЛЬСЬКОГО РЕГІОНУ 300.5 KB
  Скорочення площ посадки картоплі в сільськогосподарських підприємствах та концентрація їх переважно у господарствах населення стало негативною тенденцією яка спостерігається на всій території України.
68251. УДОСКОНАЛЕННЯ СПОСОБІВ ДОЗУВАННЯ ЕНЕРГІЇ ПРИ ФІНІШНОМУ ТЕРМОІМПУЛЬСНОМУ ОЧИЩЕННІ ПРЕЦИЗІЙНИХ ДЕТАЛЕЙ ЛІТАЛЬНИХ АПАРАТІВ 3.34 MB
  Проблема технологічного очищення поверхонь і кромок деталей високоточних механізмів від задирок мікрочастинок і мікроліквідів є актуальною для всього машинобудування. Так наприклад відомо що при забезпеченні чистоти поверхонь прецизійних деталей і робочих порожнин багатьох машин їхній ресурс можна збільшити у дватри рази.
68252. МЕТОДОЛОГІЯ ПРОГНОЗУВАННЯ РОЗВИТКУ АНОМАЛІЙ АНТРОПОГЕННОГО ПОХОДЖЕННЯ НА ОСНОВІ ЛОГІКО-АЛГЕБРАЇЧНИХ МОДЕЛЕЙ КОМПЛЕКСУВАННЯ ДАНИХ МОНІТОРИНГУ ЕКОСИСТЕМ 2.19 MB
  Методи та засоби дистанційного зондування Землі дозволяють одержувати різні види даних про об’єкти і явища в глобальному масштабі з високим просторовим і часовим розрізненням. Однак для вирішення задач що пов’язані із прогнозуванням динаміки виявлених на знімках різних об’єктів або явищ...
68253. Будівельні облицювальні вироби на основі вапняно-вапнякових композицій карбонізаційного твердіння 7.63 MB
  Єдність природного походження вапна і карбонатної вторинної сировини обумовлює однорідність структури і високу міцність композицій на їхній основі. На сьогоднішній день відсутні системні дослідження формування структури карбонізованих будівельних матеріалів на основі...
68254. ФУНКЦІОНАЛІЗОВАНІ 3,3-БІС(МЕТИЛТІО)АКРИЛОНІТРИЛИ ТА ЦІАНОАЦЕТАНІЛІДИ У СИНТЕЗІ 2-ХАЛЬКОГЕНЗАМІЩЕНИХ АМІДІВ ТА НІТРИЛІВ НІКОТИНОВОЇ КИСЛОТИ 844 KB
  Метою дослідження став синтез функціоналізованих нітрилів та амідів 2-халькогенонікотинової кислоти на основі 2-заміщених 3,3-біс(метилтіо)акрилонітрилу та СНкислот, що містять нітрильну, естерну або (селено-, тіо-)амідну групу в α-положенні в умовах реакції...
68255. ДЕТЕРМІНАНТИ ТЕХНОЛОГІЧНОГО ЛІДЕРСТВА У МІЖНАРОДНОМУ БІЗНЕСІ 392 KB
  Унаслідок цих процесів відбувалося акселероване зростання технологічної компоненти сучасного розвитку а перехід до шостого технологічного укладу країнлідерів спричинив її сингулярність в основі якої лежить штучний інтелект та застосування новітніх досягнень ІКТ...
68256. УЗАГАЛЬНЕНИЙ ІТЕРАЦІЙНИЙ АЛГОРИТМ ІНДУКТИВНОГО МОДЕЛЮВАННЯ З ЗАСТОСУВАННЯМ МЕРЕЖЕВИХ ТЕХНОЛОГІЙ 842.5 KB
  Серед різноманітних методів моделювання вирізняється метод групового урахування аргументів МГУА який дозволяє будувати моделі безпосередньо за вибіркою даних без залучення додаткової апріорної інформації.
68257. Діагностика ефективності системи корпоративного управління 307.5 KB
  Суттєві зміни в соціальноекономічному розвитку України повязані з процесами трансформації економіки посиленням конкуренції та соціальної відповідальності бізнесу на фоні загострення економічної та фінансової кризи забезпечили подальший розвиток корпоративного сектора...
68258. ОБЛІКОВО-АНАЛІТИЧНЕ ЗАБЕЗПЕЧЕННЯ УПРАВЛІННЯ БІОЛОГІЧНИМИ АКТИВАМИ САДІВНИЦТВА 229 KB
  Серед Європейських держав Україна за своїм грунтово-кліматичним потенціалом має значні переваги для розвитку інтенсивного садівництва та створення його експортного потенціалу. Такі негативні тенденції створюють передумови втрати країною потенціалу садівництва і ставлять внутрішній ринок плодів і ягід у повну залежність від їх імпорту.