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

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

.

В частности,

.


 

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

22537. Влияние различных факторов на механические характеристики материалов 54.5 KB
  Влияние процентного содержания углерода Влияние температуры окружающей среды. Повышенные температуры оказывают существенное влияние на такие механические характеристики конструкционных материалов как ползучесть и длительная прочность. Скорость релаксации напряжений возрастает при повышении температуры. Прочность углеродистых сталей с повышением температуры до 650 700oС снижается почти в десять раз.
22538. Основные понятия теории надежности конструкций 79.5 KB
  Условие прочности по существу есть условие обеспечения прочностной надежности. Например предельное напряжение входящее в условие прочности по своей природе является случайным. Если стечение обстоятельств приводящее к нарушению условия прочности редкое событие то приходим к вероятностной трактовке условия прочности с позиций теории надежности. Вместо условия прочности 1 записывается условие Р=Р 2 где Р заданное достаточно высокое значение вероятности которое называется нормативной вероятностью безотказной работы.
22539. Прочность и перемещения при центральном растяжении или сжатии 136 KB
  Напомним что под растяжением сжатием понимают такой вид деформации стержня при котором в его поперечном сечении возникает лишь один внутренний силовой фактор продольная сила Nz. Поскольку продольная сила численно равна сумме проекций приложенных к одной из отсеченных частей внешних сил на ось стержня для прямолинейного стержня она совпадает в каждом сечении с осью Oz то растяжение сжатие имеет место если все внешние силы действующие по одну сторону от данного поперечного сечения сводятся к равнодействующей направленной вдоль...
22540. Расчет статически неопределимых систем по допускаемым нагрузкам 116.5 KB
  Расчет статически неопределимых систем по допускаемым нагрузкам. Применение к статически определимым системам. Расчетная схема статически определимой стержневой системы Рассчитывая эту систему обычным путем найдем усилия N1 = N2 no формуле: из равновесия узла А. Это всегда имеет место для статически определимых конструкций при равномерном распределении напряжений когда материал по всему сечению используется полностью.
22541. Учет собственного веса при растяжении и сжатии 102 KB
  Длина стержня l площадь поперечного сечения F удельный вес материала и модуль упругости Е. Подсчитаем напряжения по сечению АВ расположенному на расстоянии от свободного конца стержня. Эти напряжения будут нормальными равномерно распределенными по сечению и направленными наружу от рассматриваемой части стержня т. Наиболее напряженным опасным будет верхнее сечение для которого достигает наибольшего значения l; напряжение в нем равно: Условие прочности должно быть выполнено именно для этого сечения: Отсюда необходимая площадь стержня...
22542. Расчет гибких нитей 148.5 KB
  Это так называемые гибкие нити. Обычно провисание нити невелико по сравнению с ее пролетом и длина кривой АОВ мало отличается не более чем на 10 от длины хорды АВ. В этом случае с достаточной степенью точности можно считать что вес нити равно мерно распределен не по ее длине а по длине ее проекции на горизонтальную ось т. Расчетная схема гибкой нити.
22543. Моменты инерции относительно параллельных осей 119.5 KB
  Моменты инерции относительно параллельных осей. Задачу получить наиболее простые формулы для вычисления момента инерции любой фигуры относительно любой оси будем решать в несколько приемов. Если взять серию осей параллельных друг другу то оказывается что можно легко вычислить моменты инерции фигуры относительно любой из этих осей зная ее момент инерции относительно оси проходящей через центр тяжести фигуры параллельно выбранным осям. Расчетная модель определения моментов инерции для параллельных осей.
22544. Главные оси инерции и главные моменты инерции 157 KB
  Главные оси инерции и главные моменты инерции. Как уже известно зная для данной фигуры центральные моменты инерции и можно вычислить момент инерции и относительно любой другой оси. Именно можно найти систему координатных осей для которых центробежный момент инерции равен. В самом деле моменты инерции и всегда положительны как суммы положительных слагаемых центробежный же момент может быть и положительным и отрицательным так как слагаемые zydF могут быть разного знака в зависимости от знаков z и у для той или иной площадки.
22545. Прямой чистый изгиб стержня 99.5 KB
  Прямой чистый изгиб стержня При прямом чистом изгибе в поперечном сечении стержня возникает только один силовой фактор изгибающий момент Мх рис. Так как Qy=dMx dz=0 то Mx=const и чистый прямой изгиб может быть реализован при загружении стержня парами сил приложенными в торцевых сечениях стержня. Сформулируем предпосылки теории чистого прямого изгиба призматического стержня. Для этого проанализируем деформации модели стержня из низкомодульного материала на боковой поверхности которого нанесена сетка продольных и поперечных рисок...