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

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

.

В частности,

.


 

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

66204. Парамиксовирусы. Вирусы парагриппа человека и эпидемического паротита 94.5 KB
  Морфология, антигенная структура. Вирусы парагриппа относятся к группе РНК-содержащих парамиксовирусов. Морфология вирусов отличается полиморфизмом, чаще встречаются вирионы округлой формы диаметром 100-300 нм. Вирусы имеют сложноорганизованную структуру, состоят из сердцевины...
66205. Выделение чистых культур аэробов. Элективные питательные среды 108 KB
  В клинической бактериологической лаборатории необходимо: Выделить бактерии в чистой культуре; Изучит их свойства; Получить достаточно бактерий для приготовления антигенов и для других исследований; Идентифицировать выделенные микроорганизмы изучая их биохимические...
66206. Лабораторная диагностика вирусных гепатитов 131 KB
  Актуальность темы: На долю вирусных гепатитов в Украине выпадает приблизительно 20% всех вирусных заболеваний, которые приводят к продолжительной потере трудоспособности: острые некрозы печени, циррозы, первичный рак печени.
66207. Изучение колоний. Пигменты бактерий 73.5 KB
  На плотных питательных средах бактерии образовывают разные по форме и величине колонии - видимые скопления микроорганизмов одного вида, которые формируются в результате размножения одной клетки. Колонии бывают плоскими, выпуклыми, куполовидными, вдавленными, их поверхность - гладкой...
66208. Онкогенные вирусы. Особенности противоопухолевого иммунитета 113 KB
  Идея о возможной роли вирусов в возникновении рака была поддержана И. Опухолеродное действие вирусов на клетки принципиально отличается от инфекционного действия и процесс вирусного канцерогенеза не является инфекционным.
66209. ВИХОВАННЯ І ШКОЛА В ЕПОХУ СЕРЕДНЬОВІЧЧЯ 64.5 KB
  Навчання починали з механічного заучування на латині молитов і 150 псалмів а потім вивчали латинську азбуку читання і письмо. Виникла така форма навчання як учнівство. Найкращим методом навчання вважався пошук найкоротшого шляху досягнення знань.
66210. Технология найма и отбора персонала 79.5 KB
  Цель набора персонала состоит в создании резерва кандидатов на все рабочие места с учетом в том числе и будущих организационных и кадровых изменений увольнений перемещений уходов на пенсию окончаний сроков контрактов изменений направлений...
66211. Модель проектной группы MSF для небольших команд 66 KB
  Задачи ролевых групп Группа Управление программой : управляет процессом разработки с целью получения готового продукта в отведенные сроки; регулирует взаимоотношения и коммуникацию внутри проектной группы; следит за временным графиком проекта и готовит отчетность о его состоянии...
66212. СТАНОВЛЕННЯ І РОЗВИТОК ЗАРУБІЖНОЇ ПЕДАГОГІЧНОЇ НАУКИ І ПРАКТИКИ У 17 – 19 СТОЛІТТЯХ 71 KB
  Вона була незалежна від церкви і держави існувала на пожертвування і високу плату за навчання. Єдиних навчальних планів не було кожна школа складала програму навчання на власний розсуд. Уряди численних німецьких держав ставились вимоги до організації початкових шкіл у містах і селах навчання хлопчиків...