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

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

.

В частности,

.


 

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

55065. Програма Power Point на уроках української мови та літератури як засіб формування інноваційної особистості 6.61 MB
  І тут на допомогу приходить візуалізація за допомогою компютерної презентації. Застосування цієї програми дає можливість учителеві та учням складати презентації для організації інформаційної підтримки під час підготовки й проведення уроківє унікальною можливістю демонстрації пропонованого матеріалу...
55066. Щастя. Як ми його розуміємо? 45 KB
  Тема: Щастя. Практична: Поглибити знання учнів про диспут та його проведення розширити розуміння поняття щастя виховувати людяність працьовитість любов до людей чесність. Щастя не слава не гроші Все це минає. Щастя це друзі хороші Шана людськая Олександр Підсуха.
55067. Грай, трембіто, дзвеніть, цимбали 533.5 KB
  Обладнання: кабінет образотворчого мистецтва зразки народних інструментів: трембіти роги цимбали; відеоматеріали. Тут грали і на скрипці і на сопілці особливо любили цимбали. У цій хаті жив і учився робити цимбали В.
55068. Всеукраїнська олімпіада з математики 795 KB
  Завдання: сформулювати і довести теореми Чеви і Менедая; показати їх застосування до доведення відомих і доведених раніше тверджень; вчити використовувати ці теореми під час розвязування задач на доведення і обчислення. Напередодні засідання учитель дає завдання трьом учням підготувати доведення тверджень про перетин в одній точці бісектрис внутрішніх кутів трикутника висот і медіан трикутника поділ кожної медіани їх точкою перетину на частини відношення довжин яких дорівнює 2:1 якщо вимірювати довжину першої частини від вершини....
55069. Позакласна робота з математики 223.5 KB
  Але вона має свої особливості: якщо урок проводиться за програмою то позакласні заняття не регламентуються нею що дозволяє вчителю підбирати завдання які відповідають рівню знань та умінь учнів здійснювати індивідуальний підхід проводити їх в цікавій формі спрямовувати на розширення поглиблення знань...
55070. Поняття про форми організації виховного процесу. Характеристика і методика проведення форм поза навчальної виховної роботи 63.5 KB
  Позакласна виховна робота - це здійснювана в позаурочний час різноманітна діяльність учнів під керівництвом учителіввихователів школи спрямована на задоволення інтересів і запитів розвиток їх інтелектуальних можливостей. Принципи на яких ґрунтується позакласна і позашкільна виховна робота Добровільний характер участі в ній учнів враховуються їх інтереси.
55071. Позакласне заняття. Весняні квіти з гофрованого паперу 34.5 KB
  Діти а для того щоб ви дізналися що ми будемо виготовляти сьогодні на занятті я вам пропоную відгадати загадки. Люблять її діти і дорослі за веселу пісеньку струмочків за дзвінкий спів птахів за ніжні проліски за мякий килим з шовкової травиці за ласкаве сонячне проміння за повітря напоєне запахом молодого листя. Діти тому сьогодні на занятті ми будемо виготовляти з паперу крокуси. Діти давайте повторимо послідовність нашої роботи.
55072. Письменники-лауреати Нобелівської премії 601 KB
  Мета: розповісти про засновника премії Альфреда Нобеля; ознайомити учнів з письменниками-лауреатами Нобелівської премії; сприяти перетворенню загальнолюдських цінностей в індивідуальний духовний досвід учнів; виховувати повагу до людської особистості, до скарбів культури; формувати гуманістичні ідеали добра.
55073. Інтелектуальне шоу «Брейн-ринг» 50 KB
  Мета: відновити в пам’яті учнів уявлення про фізичні та хвмвчні властивості хімічних речовин. Розвинути уміння працювати разом, розвинути логічне, творче мислення, увагу, пам’ять. Сформувати науковий світогляд. Виховати працелюбність, наполегливість, колективність в роботі, волю до подолання труднощів, повагу до думки іншого, інтерес до предмета.