Математическая логика и теория алгоритмов. Галуев Г.А. - 16 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 16 из 64
© 2003 Галуев Геннадий Анатольевич
Следствие. Формула А является тавтологией тогда и только тогда, когда А есть
теорема теории L.
Представленные выше результаты доказывают равносильность теории моделей
(метод интуитивных понятий или классическая пропозиционная логика) и теории до-
казательств (аксиоматический метод формальных теорий) на уровне исчисления вы-
сказываний.
В математической логике существуют и другие варианты исчисления высказыва
-
ний, в основе которых лежат другие наборы примитивных связок, другие аксиомы и
правила вывода. С ними можно ознакомиться в специальной литературе.
Рассмотрим теперь вопрос практического применения математического аппарата
исчисления высказываний в прикладных областях информатики.
Лекция №4.
Применение исчисления высказываний.
Электрические схемы.
Электрическая цепь содержащая только двухпозиционные переключатели (при
одном состоянии переключателя ток проходит через него, при другом – не проходит),
может быть представлена с помощью схемы, на которой возле каждого переключате-
ля пишется пропозиционная буква, истинностное значение которой (1 или 0) соответ-
ствует прохождению или не прохождению тока через переключатель. Тогда условие,
при котором ток
проходит через всю схему, может быть записано в виде пропозици-
онной формулы.
Например, условие, при котором ток проходит через схему на рис.1, может быть
выражено пропозиционной формулой вида
A B C
A&B&C∨D
D
Рис.1
Пропозиционной форме вида A&(B∨C)&D∨(⎤A∨⎤D)&B&(⎤D∨⎤A) соответствует элек-
трическая цепь вида
В
A D
С
⎤A ⎤D
B
⎤D A
Можно показать, что данная пропозиционная форма с помощью эквивалентных
преобразований аппарата математической логики может быть упрощена. Действи-
тельно,

Страницы