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

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

.

В частности,

.


 

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

81903. Полномочия и ответственность, делегирование полномочий 43.36 KB
  Полномочия представляют собой ограниченное право и ответственность использовать ресурсы организации самостоятельно принимать решения отдавать распоряжения и осуществлять управленческие решения. Полномочия представляются должности а не лицу её занимающему. Полномочия проявляются в виде двух общих типов: линейные; аппаратные штабные. Линейные полномочия Передаются непосредственно от начальника к подчиненному и далее по цепочке к другим подчиненным.
81904. Проблемы оптимизации соотношения централизации и децентрализации в структуре органов управления фирмы 39.29 KB
  Быстрая разработка и принятие решений адекватно отражающих реальную ситуацию максимальное использование опыта и знаний персонала более простое управление менее бюрократизированное. децентрализации: узость и тактический характер решений слабый учет или даже игнорирование в принимаемых решениях интересов других участников управления и организации в целом вследствие обособленности процесса их выработки. Таким образом появляется проблема оптимизации соотношения централизации и децентрализации проблема поиска золотой...
81905. Мотивация в менеджменте 41.86 KB
  Материальная мотивация стремление к достатку более высокому уровню жизни зависит от уровня личного дохода его структуры дифференциации доходов в организации и обществе действенности системы материальных стимулов применяемых в организации. Трудовая мотивация порождается непосредственно работой ее содержанием условиями организацией трудового процесса режимом труда. Это внутренняя мотивация человека совокупность его внутренних движущих сил поведения связанных с работой как таковой. Статусная мотивация является внутренней движущей...
81906. Эволюция подходов к мотивации в рамках научных школ управления 40.55 KB
  На основании анализа и сопоставления существующих подходов можно выделить следующие концепции мотивации в рамках которых происходила исторически оправданная эволюция понятий мотивации: традиционный подход основывающийся на использовании метода кнута и пряника и рассматривающий модели поведения человека работника: верующий человек экономический человек и механистический человек ; подход с позиций человеческих отношений основывающийся на использовании в управлении методов психологии и рассматривающий модели поведения человека ...
81907. Основные подходы к мотивации труда, используемые в менеджменте 41.1 KB
  Концепция верующего человека относится к периоду капитализма первоначального накопления состоит в том что в соответствии с духом протестантской этики при помощи веры обосновывалось поддерживалось и оправдывалось приумножение капитала честным путем как самоцель. Концепцию верующего человека в XIX в. сменила концепция экономического человека которая в упрощенном виде сводилась к тому что если работнику платить больше за сделанную работу он...
81908. Содержательные теории мотивации 41.35 KB
  К ним относятся теория иерархии потребностей А. Маслоу теория приобретенных потребностей МакКлелланда двухфакторная теория Герцберга и некоторые другие. Что касается вторичных потребностей высших уровней мотивации то несмотря на различия в формулировках все три автора содержательных теорий сходились во мнении что они активно воздействуют на поведение человека. Основными недостатками данной группы теорий является то что в реальной жизни проявление потребностей не осуществляется в строгой иерархической последовательности а является...
81910. Мотивационная теория подкрепления 40.74 KB
  Теория подкрепления исходит из того что у любого действия или поведения есть последствия: негативные и позитивные. При этом люди повторяют поведение которое приносило удовольствие было позитивно подкреплено и избегают поведения которое доставило им неприятности. Подкрепление определяется как любые действия которые вызывают повторение или напротив подавление определенных образцов поведения. Позитивное подкрепление представляет собой вознаграждение желательного для руководства организации поведения с целью формирования или закрепление у...
81911. Контроль как функция менеджмента 41.93 KB
  Существует три аспекта управленческого контроля: установление стандартов точное определение целей которые должны быть достигнуты в определенный отрезок времени. Необходимость контроля обусловлена следующими обстоятельствами: потребностью организации процесса производства в соответствии с имеющимися резервами и ресурсами; требованиями потребителей к качеству стандарту и сертификации выпускаемой продукции; изменяющимися внутренними и внешними условиями производства необходимостью выявления тенденций меняющегося спроса и предложения...