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

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

.

В частности,

.


 

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

28150. «Методика преподавания психологии»: чему и как учить 40.5 KB
  Добиться реализации данной цели на лекционных занятиях невозможно курс должен быть лекционносеминарским где на практических занятиях студенты могли бы рассматривать прикладные вопросы практики обучения связанные с сохранением психического здоровья учащихся с созданием благоприятного психологического климата на уроке с возможностями объективного оценивания эффективности образовательного процесса. Однако не учитывая изменения эмоционального состояния ребенка динамику состояния соматического здоровья нельзя судить о качестве учебного...
28151. Проблема психической нормы и патологии 44 KB
  Вопрос определения нормы и патологии является крайне сложным и затрагивает различные сферы человеческой деятельности от медицины и психологии до философии и социологии. Был совершён ряд попыток вывести критерии психической нормы в число которых включали соответствующую возрасту человека зрелость чувств адекватное восприятие действительности наличие гармонии между восприятием явлений и эмоциональным отношением к ним умение уживаться с собой и социальным окружением гибкость поведения критический подход к обстоятельствам жизни наличие...
28152. Периодизация интеллектуального развития ребёнка (по Ж.Пиаже) 33.21 KB
  Швейцарский теоретиккогнитивист Жан Пиаже 1896-1980 был пионером в этой области исследований. С точки зрения Пиаже интеллект не просто реагирует на раздражители: скорее он растет меняется и адаптируется к миру. Пиаже и других когнитивных психологов называют структуралистами поскольку их интересует структура мышления и то каким образом интеллект перерабатывает информацию. Напротив когнитивные структуры Пиаже являются абстрактными и гипотетическими.
28153. Теоретические и психотерапевтические концепции Роджерса и Франкла 63 KB
  Этот мир создаваемый человеком может совпадать или не совпадать с реальной действительностью так как не все предметы в окружении человека осознаются им. Говоря о структуре Я Роджерс пришел к выводу о том что внутренняя сущность человека его Самость выражается в самооценке которая является отражением истинной сути данной личности его Я. Исследования проведенные Роджерсом доказывали что успешная социализация человека его удовлетворение работой и собой коррелируют с Уровнем его самосознания. При этом Роджерс не только говорит о...
28154. История развития представлений на природу способностей 58.5 KB
  История развития представлений на природу способностей Само понятие способности ввел в науку Платон. Источник развития способностей помещается внутрь человека они обусловлены наследственным генетическим фактором. К теориям преформизма примыкают и воззрения испанского врача Хуана Уарте Исследование способностей к наукам 1575 год. Уарте также говорил о врожденности способностей: Пусть плотник не занимается земледелием а ткач архитектурой; пусть юрист не занимается лечением а медик адвокатским делом; но пусть каждый занимается только...
28155. Процесс психологического консультирования. Принципы, структура, техники 114.5 KB
  Цель консультирования помочь клиентам понять происходящее в их жизненном пространстве и осмысленно достичь поставленной цели на основе осознанного выбора при разрешении проблем эмоционального и межличностного характера . В консультировании акцентируется ответственность клиента т. признается что независимый ответственный индивид способен в соответствующих обстоятельствах принимать самостоятельные решения а консультант создает условия которые поощряют волевое поведение клиента. СТРУКТУРА ПРОЦЕССА КОНСУЛЬТИРОВАНИЯ Ни одна из...
28156. Проблема психологического «выгорания», копинг-стратегии 64.5 KB
  Проблема психологического выгорания копингстратегии. Совладающее поведение копингстратегии. Проблема копинга совладания личности с трудными жизненными ситуациями возникла в психологии во второй половине ХХ века. В настоящее время будучи свободно употребляемым в различных работах понятие копинг охватывает широкий спектр человеческой активности от бессознательных психологических защит до целенаправленного преодоления кризисных ситуаций.
28158. Психологические признаки трудовой деятельности 28 KB
  Климов выделяет четыре психологических признака трудовой деятельности: Сознательное предвосхищение социально ценного результата. Таким образом установим некоторую структуру рассматриваемого первого признака труда и будем различать в нем три компонента которые примем как относительно самостоятельные: а более или менее ясное знание о продукте деятельности б более или менее четкое осознание его социальной ценности в более или менее выраженный аффективный тон соответствующих знаний представлений образов. Деятельность становится трудом...