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

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

.

В частности,

.


 

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

83071. Роль менеджмента и управления. Модели менеджмента 83.46 KB
  Менеджмент – моделирование или разработка и социально-экономических систем, их управление, с целью как можно эффективнее их использовать. Главной задачей менеджмента является достижение эффективности производства путем улучшения потребления ресурсного потенциала организации.
83072. Разработка сцинтилляционного детектора нейтронного излучения 1.65 MB
  Стремительное развитие электроники и вычислительной техники оказалось предпосылкой для широкой автоматизации самых разнообразных процессов в промышленности, в научных исследованиях, в быту. Реализация этой предпосылки в значительной мере определялась возможностями устройств для получения...
83073. Теоретические аспекты мерчандайзинга на торговом предприятии 2.2 MB
  Система мерчандайзинга применяется как на малых торговых предприятиях так и больших таких как ОАО Магнит. В данной главе курсовой работы будет проанализирована маркетинговая деятельность а также рассмотрены все инструменты мерчандайзинга используемые в розничной сети Магнит города Оренбург.
83074. Документообіг залізничного транспорту 1.1 MB
  Вантажна і комерційна робота як виробнича сфера залізничного транспорту і як галузь експлуатаційної науки має свою більш як столітню історію розвитку. Вона займає важливе місце в експлуатаційній діяльності залізничних доріг і включає комплекс питань, пов’язаних з перевізним процесом...
83075. Правовые механизмы деятельности российских и зарубежных профсоюзных организаций 60.06 KB
  Для профсоюзов основной задачей является защита трудовых и иных социальных прав граждан во взаимоотношениях с теми или иными государственными органами работодателями и их объединениями. В силу указанного для профсоюзов очень важное значение будет иметь завершение процесса обретения полной...
83076. Решение задач по закону нормального распределения при помощи редактора электронных таблиц MS Excel 422.04 KB
  Курсовая работа на тему экспериментальный метод в методологии исследования. Данная работа включает в себя: 4 задачи по теории вероятности, 2 задачи по закону нормального распределения, задачу по системам массового обслуживания.
83077. ИЗМЕРЕНИЕ ТЕПЛОЕМКОСТИ ТЕЛ 101 KB
  При нагревании на датчике 3 установки через каждые 4 с выводятся значения напряжения и силы тока нагревателя, что позволяет определить мощность и количество теплоты, выделившейся на нагревателе. Установка запоминает значения температуры стакана и цилиндра через каждые 4 с, строит графики зависимости...
83078. Технологический процесс построения модели в MatLab 564.5 KB
  Задачи управления: стабилизация на заданном уровне, наблюдение (определение траектории движения, перемещения объекта), настройка параметров или экспериментальное управление (достижение минимальных и максимальных параметров, постоянных во времени), программное управление (обеспечение наперед заданного поведения объекта).
83079. Анализ доходной и расходной частей федерального бюджета РФ за 2012-2014 года 341 KB
  Социально-экономические преобразования происходящие в современной России заставляют критически подойти к постулатам и стереотипам лежащим в основе экономической теории и заново осмыслить законы общественного воспроизводства отражающие связи и зависимости между различными элементами экономической системы.