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

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

.

В частности,

.


 

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

24422. Координатор МАКЕ и система управления исходным кодом SCCS 110.5 KB
  Описание взаимозависимостей содержит команды которые должны быть выполнены если обнаружится что некоторый модуль устарел перестал соответствовать действительности. Такие команды обеспечивают реализацию всех необходимых для модернизации модуля действий. В одних системах интерпретатор прост но совокупность команд не образует язык программирования а в других имеются отличные языки программирования на уровне системных команд но выполнение отдельной команды осложнено. Контрольная точка задается для конкретной формы доступа к памяти...
24423. Общая характеристика основных компонентов ОС ПЭВМ 93 KB
  Сетевой уровень занимает в модели OSI промежуточное положение: к его услугам обращаются протоколы прикладного уровня сеансового уровня и уровня представления. Для выполнения своих функций сетевой уровень вызывает функции канального уровня который в свою очередь обращается к средствам физического уровня. Физический уровень выполняет передачу битов по физическим каналам таким как коаксиальный кабель витая пара или оптоволоконный кабель. Канальный уровень обеспечивает передачу кадра данных между любыми узлами в сетях с типовой топологией...
24424. Таймеры счётчики ОМЭВМ 204 KB
  Основным отличием конфигураций сетей Fast Ethernet является сокращение диаметра сети примерно до 200 м что объясняется сокращением времени передачи кадра минимальной длины в 10 раз за счет увеличения скорости передачи в 10 раз по сравнению с 10мегабитной сетью Ethernet. Если среда свободна то узел имеет право начать передачу кадра. Последний байт носит название ограничителя начала кадра. Наличие двух единиц идущих подряд говорит приемнику о том что преамбула закончилась и следующий бит является началом кадра.
24425. Основные компоненты современных систем баз данных. Классификация и модели данных, реализуемых в СУБД 318 KB
  Классификация и модели данных реализуемых в СУБД. База данных это данные организованные в виде набора записей определенной структуры и хранящиеся в файлах где помимо самих данных содержится описание их структуры. Метаданные Данные о структуре базы данных.
24426. Язык манипулирования данными, концепции и возможности языка SQL. Функции администратора баз данных 181.5 KB
  Перечисленные устройства передают кадры с одного своего порта на другой анализируя адрес назначения помещенный в этих кадрах. По адресу источника кадра коммутатор делает вывод о принадлежности узлаисточника тому или иному сегменту сети. Одновременно с передачей кадра на все порты коммутатор изучает адрес источника кадра и делает запись о его принадлежности к тому или иному сегменту в своей адресной таблице. При каждом поступлении кадра на порт коммутатора он прежде всего пытается найти адрес назначения кадра в адресной таблице.
24427. Адреса и сети Интернет. Архитектура и методы использования баз данных на Web 52 KB
  10277 Стадии разработки: постановка задачи стадия Техническое задание; анализ требований и разработка спецификаций стадия Эскизный проект; проектирование стадия Технический проект; реализация стадия Технический проект. Проектирование. Процесс проектирование сложного ПО обычно включает: проектирование общей структуры определение основных частей компонентов и их взаимосвязей по управлению и данным; декомпозицию компонентов и построение структурных иерархий в соответствии с рекомендациями блочноиерархического подхода;...
24428. Классификации сайтов. Сервисы Интернет 40.5 KB
  Сервисы Интернет. Классификация сайтов Все многообразие информации в интернете обозначаемой одним емким словом сайт можно условно разделить по: задачам сайта цели его создания и фунционирования коммерческий некоммерческий информационный рекламный поисковая система. объемности хоумпейдж сайтывизитки интернетпредставительства вебпорталы и т. Интернет сервисы: Пользователь работающий в Интернет имеет дело с несколькими различными видами услуг.
24429. Концепция и возможности XML-технологий 67 KB
  Концепция и возможности XMLтехнологий. XML Extensible Markup Language[1] это язык разметки описывающий объектов данных называемых XML документами. сам по себе XML не содержит никаких тэгов предназначенных для разметки он просто определяет порядок их создания. Таким образом если например мы считаем что для обозначения элемента rose в документе необходимо использовать тэг flower ; то XML позволяет свободно использовать определяемый нами тэг и мы можем включать в документ фрагменты подобные следующему: flower rose flower Набор...
24430. Архитектура стека TCP/IP. Протокол IP. Заголовок IP-пакета. IP-адресация 238.5 KB
  Заголовок IPпакета. В его задачу входит продвижение пакета между сетями от одного маршрутизатора до другого до тех пор пока пакет не попадет в сеть назначения. Заголовок IPпакета IPпакет состоит из заголовка и поля данных. Значение длины заголовка IPпакета также занимает 4 бита и измеряется в 32 битовых словах.