5.8.2. Применение исчисления высказываний в конструировании релейно-контактных схем

Исчисление высказываний нашло широкое применение в теории и практике конструирования релейно-контактных схем благодаря основному свойству высказываний – высказывание может быть либо истинно, либо ложно. «Контакт» в электроцепи также выполняет две функции – пропускать либо не пропускать электрический ток. Поэтому можно каждому «контакту» поставить в соответствие некое высказывание, такое что, когда «контакт» пропускает ток, высказывание истинно, а когда не пропускает – ложно:

Последовательное соединение «контактов» соответствует логической операции «и», а параллельное соединение – «или»:

Последовательное соединение аÙb

Произвольная комбинация соединений дает формулу исчисления высказываний, например, аÙbÙ(сÚd):

Таким образом, структурная форма любой контактной схемы – это формула исчисления высказываний. Основная задача теории контактных схем – отыскание схемы, логически эквивалентной данной схеме, так, чтобы можно было выбрать наиболее подходящую.

В этих операциях действуют основные законы исчисления высказываний, например, закон исключения третьего:

5.9. Контрольные вопросы и упражнения

1. Определите исчисление высказываний как формальную систему.

2. Что такое семантическое дерево?

3. Какие существуют классы формул в исчислении высказываний?

4. Перечислите алгоритмы доказательства общезначимости и невыполнимости формулы исчисления высказываний.

5. Существует ли универсальный алгоритм доказательства выполнимости формулы исчисления высказываний?

6. Чем различаются логический и алгебраический подходы к определению класса формулы?

7. В чем заключается ограниченность исчисления высказываний?

8. С помощью алгоритма Куайна проверьте общезначимость следующей формулы (p (q  r))  ((pq) (pr)).

9. С помощью алгоритма редукции проверьте общезначимость следующей формулы (p(qr))((ps)r).

10. Приведите формулу к КНФ (pÚq)  (ùqÚr).

11. Приведите формулу к ДНФ pÚ(q  ù r).

12. Примените принцип резолюций к множеству дизъюнктов, полученному в задании 10.

6. Исчисление предикатов

Уже упоминавшийся выше силлогизм «Люди смертны …» не может быть представлен с помощью исчисления высказываний. Для его формализации необходимо ввести квантифицированную переменную «человек», причем множественность, отражающаяся в первой посылке силлогизма, указывает на ее универсальность: «Всякий х, который обладает свойством «человек», смертен».

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

(х) (человек (х)  смертен (х)),

где х является квантифицированной или связанной переменной, а выражения «человек» и «смертен» являются предикатами. Формальная система, соответствующая изложенным выше требованиям, называется исчисление предикатов первого порядка (или просто исчисление предикатов) – это расширение логики высказываний, в котором высказывания расчленяются на субъект и предикат. Субъект – это то, о чем что-то утверждается. Предикат – это то, что утверждается о субъекте (свойство субъекта).