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

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

.

В частности,

.


 

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

23550. РУССКИЙ ЯЗЫК И КУЛЬТУРА РЕЧИ 1.42 MB
  Русский язык и культура речи Речевое взаимодействие. Нормативные коммуникативные этические аспекты устной и письменной речи. Культура речи.
23552. РУССКИЙ ЯЗЫК И КУЛЬТУРА РЕЧИ. ТЕОРЕТИЧЕСКИЙ КУРС 376 KB
  МЕТОДИЧЕСКАЯ ЗАПИСКА Данное пособие является частью комплекса учебных пособий по русскому языку и культуре речи. В нем представлен теоретический материал предусмотренный программой по русскому языку и культуре речи. Рассматриваются различные аспекты речевой культуры формы существования языка стили современного русского языка характеризуются особенности официальноделовой речи основные черты языка юридических текстов излагаются основы ораторского искусства.
23553. Курс русской риторики 1 MB
  Перечитывая и осмысляя эту книгу читатель подружится с ней на долгие годы. Слово ητρική значает ораторское искусство или учение об ораторском искусстве но главным содержанием риторики уже в то время была теория аргументации в публичной речи. Грамматика наука об общих правилах построения осмысленной речи. Риторика наука об аргументации в публичной речи необходимой при обсуждении вопросов практического характера.
23554. Выразительность и ее основные условия 128 KB
  Выразительность речи зависит от многих причин и условий собственно лингвистических и экстралингвистических. Одним из основных условий выразительности является самостоятельность мышления автора речи что предполагает глубокое и всестороннее знание и осмысление предмета сообщения. В значительной степени выразительность речи зависит и от отношения автора к содержанию высказывания.
23555. ОБЩАЯ РИТОРИКА 2.01 MB
  Объектом этой теории является изучение дискурсивных приемов позволяющих вызвать или усилить сочувствие к предложенным для одобрения положениям Perelman 1958 с. Главы посвященные детальнейшему разбору четырех типов риторических метабол представляют собой образец блестящего анализа живого функционирования языка а значение совокупности содержащихся в них наблюдений эвристических ходов мысли далеко выходит за рамки проблематики даже столь сложного феномена каким является литературный художественный язык. Если с известной долей...
23556. ИСКУССТВО ОРАТОРА 1.93 MB
  Савкова ИСКУССТВО ОРАТОРА СОДЕРЖАНИЕ Введение Удивительный дар природы Оратор и его голос Что ни звук то и подарок Дикция оратора Порусски ли мы говорим Литературное произношение Косноязычна риторика без грамматики Языковая культура Мое богатство мой язык Языковые средства выразительности От сердца к сердцу нити проложить Интонационная выразительность Язык чувств Жесты и мимика как средство общения С пером в руке Как создать текст выступления Посмеемся вместе Юмор в публичном...
23557. Культура речи 1.01 MB
  Чтобы передать ее другому он произносит слова. Мужик либо не отвечал ничего либо произносил слова вроде следующих: А мы могим. Речь Базарова строится по нормам литературного языка в ней встречаются отвлеченные книжные слова непонятные собеседнику: воззрение будущность излагать эпоха история закон. Не случайно в древнерусском языке одно из значений слова смысл было разум рассудок ум.
23558. КУЛЬТУРА РУССКОЙ РЕЧИ 3.36 MB
  Виноградова КУЛЬТУРА РУССКОЙ РЕЧИ Учебник для вузов Ответственные редакторы – доктор филологических наук профессор Л. Бурвикова Культура русской речи. ISBN 5891231867 ISBN 5862257055 Книга представляет собой первый академический учебник по культуре речи содержащий наиболее полный систематизированный материал по данной теме. В основе издания лежит принципиально новая теоретическая концепция культуры речи.