Множества, отображения, логика



страница5/6
Дата26.11.2012
Размер0.77 Mb.
ТипДокументы
1   2   3   4   5   6


4.23. Нормальные формы. Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию отдельных переменных или их отрицаний, входящих в данный член не более одного раза.

Соглашение. Условимся знак конъюнкции не писать, т.е. вместо записывать просто АВ.

Данная формула приводится к ДНФ посредством: 1) законов де Моргана (отрицание должно быть только у отдельных переменных); 2) первого закона дистрибутивности; 3) тождеств: ХХ = Х, .

Пример 8.





.■

Члены ДНФ, представляющие собой элементарные конъюнкции k букв, называются минитермами k-го ранга. Так, в примере 8 член ху — минитерм второго ранга, — минитерм третьего ранга.

Если исходная формула содержит другие операции (импликацию, эквиваленцию), то они предварительно выражаются через конъюнкцию, дизъюнкцию и отрицание с помощью формул (см. п. 4.8):

,

.

4.24. Совершенные нормальные формы. Если в каждом члене ДНФ представлены все переменные (с отрицанием или без), то она называется совершенной дизъюнктивной нормальной формой (СДНФ).

Можно доказать, что любая булева функция, не являющаяся тождественным нулем, имеет одну и только одну СДНФ.

Если какой-либо слагаемое  данной ДНФ не содержит переменной х, то  заменяется на эквивалентное слагаемое ( = . В силу тождеств gif" name="object185" align=absmiddle width=129 height=18>, одинаковые слагаемые, если они появляются, заменяются одним таким слагаемым.

Пример 9. Продолжая пример 8, приведем полученную функцию к СДНФ:

=



=

.

Попутно заметим, что из полученной СДНФ получается интересная формула: , как будто член лишний в левой части. На самом деле это действительно так, ибо как мы только что выяснили

,

при этом

.■

4.25. Принцип двойственности применительно к математической логике гласит: Если две данные формулы равносильны, то равносильными будут и формулы, получающиеся из данных заменами:

конъюнкция дизъюнкция,

дизъюнкция конъюнкция,

0  1,

1  0.

Пример 10. Формуле двойственна формула .

Пример 11. Формуле двойственна формула .

Примечание. Принцип двойственности имеется во многих науках и, в частности, в теории множеств, в которой операции пересечения и объединения являются взаимно двойственными. В геометрии принцип двойственности помогает из доказанной теоремы получать двойственную теорему, справедливость которой следует из справедливости исходной теоремы и принципа двойственности. Последний в случае (проективной) двумерной геометрии гласит: «Если верна теорема А, в которой говорится о точках и прямых, то верна двойственная теорема А*, которая получается из теоремы А взаимной заменой слов «точка» «прямая», «точка пересечения прямых» «прямая, проходящая через точки». Ярким примером служит:

Теорема (Дезарг). Если между вершинами двух данных треугольников установлено взаимно однозначное соответствие и три прямые, соединяющие соответственные вершины, пересекаются в одной точке, то три точки пересечения соответственных сторон треугольников лежат на одной прямой (рис. 7).

Двойственная теорема запишется так: Если между сторонами данных треугольников установлено взаимно однозначное соответствие и три точки пересечения соответственных сторон лежат на одной прямой, то три прямые, соединяющие соответственные вершины, пересекаются в одной точке.



4.26. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х и у). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается. Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т.е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим и .

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х и у, а состояния лампочки — со значением функций этих переменных.

4.27. Задача. Булева функция f (x, y, z) задана таблицей истинности:

х

y

z

f (x, y, z)

1

1

1

0

1

1

0

1

1

0

1

0

1

0

0

0

0

1

1

1

0

1

0

1

0

0

1

0

0

0

0

1

Требуется: 1) записать функцию f формулой, 2) упростить ее (если это возможно), 3) проверить результат с помощью таблицы истинности, 4) построить граф переключательной схемы для функции f.

Решение. □ 1) Будем искать функцию f в СДНФ, представив ее в виде дизъюнкции всевозможных минитермов третьего ранга:

.

Однако если оставить f в таком виде, мы не получим правильного решения. Следовательно, некоторые минитермы нужно удалить, используя данную таблицу. Из первой строки следует, что при (x, y, z) = (1, 1, 1) функция f равна 0, в то время как минитерм xyz равен 1; следовательно, этот минитерм не может входить в дизъюнкцию f. Аналогично рассуждая, мы приходим к выводу, что минитермы , , не должны входить в f. Таким образом, .

2) Упростим найденную функцию:



.

3) Проверим результат с помощью таблицы истинности; при этом значения найденной функции запишем в предпоследнем столбце, а данной функции — в последнем:

х

y

z













f (x, y, z)

1

1

1

0

0

0

0

0

0

0

1

1

0

1

0

1

1

0

1

1

1

0

1

0

0

0

0

0

0

0

1

0

0

1

0

1

0

0

0

0

0

1

1

0

1

1

1

0

1

1

0

1

0

0

0

0

0

1

1

1

0

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

Сравнивая построчно последние два столбца, заключаем, что найденная функция равна данной.


4) Граф переключательной схемы представлен на рис. 9.■




Задание 4. Булева функция Fn(x, y, z) задана таблицей истинности:


х

y

z

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

1

1

1

0

1

0

1

1

0

0

1

1

1

1

1

1

0

0

1

1

0

1

0

1

1

1

0

0

0

0

1

0

1

0

1

1

1

0

1

1

1

0

0

1

0

1

1

0

0

0

0

0

1

0

1

0

0

1

0

1

1

0

1

1

0

1

1

0

0

1

1

1

0

1

1

1

0

0

0

0

0

1

1

0

0

0

0

1

1

1

0

1

0

1

1

1

1

0

1

1

0

0

0

1

1

1

0

0

0

0

1

1

1

1

1

1

1

0

0

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

0

1

1

0

1

0

1

0

0




х

y

z

F16

F17

F18

F19

F20

F21

F22

F23

F24

F25

F26

F27

F28

F29

F30

1

1

1

1

1

0

1

0

0

1

1

0

0

0

1

1

1

1

1

1

0

1

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

0

1

1

1

0

1

0

1

0

1

1

1

1

1

1

1

1

1

0

0

0

1

1

1

1

0

0

1

1

1

0

0

0

1

1

0

1

1

0

0

1

0

1

0

0

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

1

0

0

1

0

1

1

0

0

0

0

0

0

1

0

0

0

1

1

1

1

1

0

0

1

1

0

0


Требуется: 1) записать функцию f формулой, 2) упростить ее (если это возможно), 3) проверить результат с помощью таблицы истинности, 4) построить граф переключательной схемы для функции f. Примечание: для варианта номер n предназначена функция Fn.■

Библиографический словарь
Аристотель [якобы 384 – 322 до н. э.] — греческий ученый, участник Академии Платона, основатель философской школы в Афинах, оказавшей большое влияние на всё последующее развитие многих наук. Воспитатель Александра Македонского. Охватил почти все доступные для его времени отрасли знания. Дал первое систематическое построение и изложение логики, в частности теории доказательств. Исследовал идеи потенциальной и актуальной бесконечности, непрерывного и дискретного количества, зан
имался некоторыми вопросами геометрии. (Зубов В. П., Аристотель.— М.: 1963.) С другой стороны, Аристотель — безымянный мираж (аРиСТоТеЛь = РСТТЛ = РоСТиТеЛь = роститель = учитель); Прокл Диадох в комментариях к «Началам» Евклида упоминает о неком старшем Аристотеле; тогда, надо полагать, младший Аристотель также существовал и был ростителем Александра Македонского; вооруженные молчанием историки обязаны пропустить сие замечание без комментариев,— ибо их профессионализм, как правило, заключается в том, чтобы ничего научно не доказывать, а лишь ссылаться на труды своих ростителей, которые ссылались на трактаты своих ростителей и т.д.
Б

уль
Джорж (Boole George) [2.11.1815, Линкольн,— 8.12.1864, Баллинтемпл, близ Корка] — английский математик и логик. Не имел специального математического образования, с 1849 проф. математики в Куинс-колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной мере интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские идеи Аристотеля и Цицерона. В работах «Математический анализ логики» («The mathematical analysis of logic…», Cambridge, 1849), «Исследование законов мышления» («An investigation of the laws of thought…», L., 1854), Буль заложил основы математической логики. Именем Буля названы т.н. булевы алгебры — особые алгебраические системы, для элементов которых определены две операции.
Гильберт Давид [Hilbert David) [23.1.1862, Велау, близ Кёнигсберга,— 12.14.1943, Гёттинген] — немецкий математик. «Основания геометрии» Гильберта (1899) стали образцом для дальнейших работ по аксиоматическому построению математических теорий.




Кантор Георг (Cantor Georg) [3,3.1845, Петербург,— 6.1.1918, Галле] — немецкий математик. Создал теорию множеств, ввел понятие мощности множества, привел пример фрактала — множества кантора.

Лейбниц Готфрид Вильгельм (1.7.1646, Лейпциг,— 14.11.1716, Ганновер) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. Реальный мир, по Лейбницу, состоит из бесчисленных психически деятельных субстанций — монад, находящихся между собой в отношении предустановленной гармонии; существующий мир создан богом как «наилучший из всех возможных миров». В логике Лейбниц р
азвил учение об анализе и синтезе, впервые сформулировал закон достаточного основания, ему принадлежит также принятая в современной логике формулировка закона тождества. Лейбниц создал наиболее полную для того времени классификацию определений, разработал теорию генетических определений. В работе Лейбница «Рассуждение о комбинаторном искусстве» («Dissertatio de arte combinatoria», Lipsiae, 1666) предвосхищены некоторые моменты современной математической логики; Лейбниц выдвинул идею применения в логике математической символики и построений логических исчислений, поставил задачу логического обоснования математики, предложил использовать двоичную систему счисления для целей вычислительной математики. Лейбниц впервые высказал мысль возможности машинного моделирования человеческих функций, ввел термин «модель». В математике важнейшей заслугой Лейбница является разработка (наряду с И. Ньютоном) дифференциального и интегрального исчисления, имевшая огромное значение для дальнейшего развития математики и естествознания. Лейбниц ввел современные знаки дифференциала d и интеграла ∫.
Прокл Диадох (якобы ок.410, Константинополь,— 485, Афины) — византийский математик и философ. Дал обзор истории геометрии от Фалеса до Евклида. Сформулировал и пытался доказать V постулат Евклида.

В
от что пишет А.Ф. Лосев [Лосев А.Ф. История античной эстетики. Т.7. Кн.1.— М.: 1988.— 414 с.] о неоплатонике Прокле: «Прокл является поклонником триады, энтузиастом триады, постоянным воспевателем триады и её восторженным, неистовым служителем, певцом, жрецом, мистагогом... Философская эстетика Прокла есть священный трепет перед триадами».


1   2   3   4   5   6

Похожие:

Множества, отображения, логика iconФакультет
Отображения множеств. Счетные и несчетные множества. Функции множества. Мера множества. Измеримые множества и функции. Интеграл Лебега....
Множества, отображения, логика iconУчебно-методическое пособие Саранск 2012 Отображения. Функции Сведения из теории
Пусть даны некоторые множества и. Бинарное соответствие из в называется отображением множества в множество, если
Множества, отображения, логика iconМатематический анализ
Множества. Декартово произведение двух множеств. Отображения функции, обратная функция. Эквивалентность множеств. Счетность множества...
Множества, отображения, логика iconПрограмма курса дифференциальная топология и риманова геометрия
Топология, топологическое пространство. Гомеоморфизм, сравнение топологий. Открытые и замкнутые множества. Внутренность, замыкание...
Множества, отображения, логика iconГруппы: мк-301, мт-301
Понятия множества и отображения, способы задания множеств. Алгебра множеств и подмножеств. Теорема об отображении множества самого...
Множества, отображения, логика icon1 Содержание дисциплины
Множества, подмножества. Булевы операции над множествами и их свойства. Законы Д’Моргана. Отношения, функциональные отношения, отображения....
Множества, отображения, логика iconМножества и операции со множествами. Понятие множества и мультимножества
Цель таких описаний отразить важнейшие (атрибутные) свойства множества, а именно: разли­чимость всех частей множества, неупорядоченность...
Множества, отображения, логика iconПрограмма государственного экзамена Направление подготовки 230400 «Прикладная математика»
Отображения. Инъективные, сюръективные и биективные отображения. Теорема о произведении (композиции) отображений. Критерий существования...
Множества, отображения, логика icon1-й и 2-й семестры Множества и отображения
Множество и его элементы. Примеры множеств. Отношение включения и его свойства. Операции над множествами: пересечение, объединение,...
Множества, отображения, логика iconРоберт столл множества. Логика. Аксиоматические теории

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org