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

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

.

В частности,

.


 

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

42893. Дослідження цільових програм готельного обслуговування в Україна та світі 108.1 KB
  Ринок туристичних послуг€ провадиться описання характерних типів сегментованого ринку Любіцева О. Ринок туристичних послуг. Навчальний посібник “Уніфіковані технології готельних послуг†знадобився авторові при виділенні сукупності факторів що впливають на комплексність надання послуг у готельних підприємствах Лук‘янова Л.
42894. Моделирование динамических систем 652.61 KB
  Модель несёт системообразующую и смыслообразующую роль в научном познании. На модели изучают неизвестные свойства предметов. Модель стремится как можно более ярко выразить структуру явления, его главные аспекты; является концентрированным выражением сущности предмета или процесса, выделяя только его основные черты.
42895. Информационная система Проверка выполнения плана отгрузки продукции заказчикам 3.92 MB
  В процессе договорной компании составляется договор на поставку товаров. Договор состоит из двух частей: общей части, включающей в себя реквизиты заказчика и поставщика, предмет поставки и т. д. , и спецификации, в которой приводятся подробные сведения о товарах и сроках поставки. На основе договоров составляется финансовый план и разрабатываются цеховые помесячные планы выпуска товарной продукции.
42896. Методы и способы измерения толщины окисных пленок, диффузионных и эпитаксиальных слоев, их физические основы 851 KB
  Совершенствование технологии производства полупроводниковых материалов и приборов связано с необходимостью повышения точности и экспрессности лабораторного и промышленного контроля их электрофизических параметров. От качественных характеристик измерительной техники зависит уровень технологических потерь на различных этапах производства.
42897. Совершенствование учетной политики для целей налогообложения на примере ООО «Апекс» 144.45 KB
  Роль и значение налогового учета на предприятии 1.1 Понятие налогового учета цели задачи.2001 №110ФЗ 25 глава НК произошло законодательное закрепление ведения налогового учета. Налоговый учет доходов и расходов для целей исчисления налога на прибыль отделен от бухгалтерского учета и становится самостоятельным направлением учета фактов хозяйственной жизни организаций.
42898. The United States of America 52.88 KB
  The United States of America (also called the United States, the U.S., the USA, America, and the States) is a federal constitutional republic comprising fifty states and a federal district. The country is situated mostly in central North America, where its forty-eight contiguous states and Washington, D.C., the capital district, lie between the Pacific and Atlantic Oceans, bordered by Canada to the north and Mexico to the south. The state of Alaska is in the northwest of the continent, with Canada to the east and Russia to the west, across the Bering Strait.
42899. УПРАВЛЕНИЕ ПЕРСОНАЛОМ 46.06 KB
  Курсовая работа является самостоятельной научной работой студента и должна отражать приобретенные им знания и результаты исследования по общим и специальным разделам управления персоналом в рамках выбранной темы. Тематика курсового проектирования определяется программой дисциплины «Управление персоналом».
42900. Графіки в економічному моделюванні 140.48 KB
  В умовах ринкової системи управління виробничою і збутовою діяльністю підприємств і фірм в основі прийняття господарських рішень лежить ринкова інформація, а обгрунтованість рішень перевіряється ринком у ході реалізації товарів і послуг. При такому підході початковим пунктом усього циклу підприємницької діяльності стає вивчення споживчого попиту. Розглянемо деякі питання моделювання попиту і споживання.
42901. Бухгалтерский учет расчетов с бюджетом и внебюджетными фондами в ООО «Золотой Флок» 12.09 MB
  Еще Ф. Аквинский, известный церковный деятель и философ XIII в. высказывался о проблемах установления и сбора налогов следующим образом: он определял налоги, как «дозволенную форму грабежа». Речь идет о том, что взимание налогов всегда ущемляет чьи-то интересы и в определенной степени отягощает социальное положение.