Дискретная математика

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Тему завершим небольшим параграфом, в котором изложим применение логики высказываний к анализу так называемых контактных схем.


Контактом будем называть устройство, которое в процессе работы может быть в двух состояниях: контакт может быть замкнут или разомкнут. Контакт Х на чертеже будем изображать следующим образом:



Контакты можно соединять между собой различными способами:



Первое соединение называется параллельным, второе – последовательным. Контакты, соединенные между собой, будем называть контактной схемой. Будем предполагать наличие у схемы двух выделенных точек входа и выхода. Схему назовем замкнутой, если существует последовательность замкнутых контактов Х12,...,Хn такая, что Xi соединен с Хi+1, X1 соединен с входом, Хn – с выходом. Схему, не являющуюся замкнутой, назовем разомкнутой. Каждому контакту поставим в соответствие высказывание, которое истинно тогда и только тогда, когда контакт замкнут. Высказывание и контакт будем обозначать одной буквой. Пусть схема S построена из контактов Х12,...,Хn с помощью параллельного и последовательного соединений. Тогда по схеме S можно построить формулу логики высказываний FS так, что параллельному соединению соответствует дизъюнкция, последовательному – конъюнкция. Например, схеме S0 соответствует формула



FS0=X&(ZÚØY)]Ú[ØX&Z]Ú[(XÚØY)&ØZ].


(Через ØV обозначается контакт, который замкнут тогда и только тогда, когда V разомкнут). Формула FS "представляет схему в следующем смысле: схема S замкнута в том и только в том случае, если Fs принимает значение И. Контактным схемам соответствуют формулы, в построении которых участвуют лишь связки &,Ú,Ø, причем отрицание применяется только к атомарным формулам. Нетрудно понять, что по всякой такой формуле F можно восстановить схему, которую формула F «представляет».

Пусть схемам S и T соответствуют формулы FS и FT в описанном выше смысле. Тогда если схемы S и T эквивалентны (т.е. замкнуты и разомкнуты одновременно), то FS и FT равносильны, и обратно. Этот факт используется для решения задачи минимизации контактных схем, которая состоит в том, чтобы по данной схеме S найти схему Т, эквивалентную S и содержащую меньше контактов. Один из путей решения этой задачи состоит в переходе к формуле FS и в отыскании формулы G, равносильной FS и содержащей меньше вхождений атомарных формул (разумеется, G построена только с помощью &, Ú и Ø, причем Ø применяется лишь к атомарным формулам). Так, например, формула FS равносильна формуле ХÚ(ØX&Z)Ú(ØY&ØZ). Следовательно, приведенная выше схема эквивалентна следующей схеме



которая состоит на три контакта меньше.

Задачи

Ответы, указания и решения

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru