Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Знание действия зависит от знания причины и заключает в себе последнее. Б. Спиноза Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ § 1. Логическое следствие и проблема дедукции в логике высказываний Пусть Л и в - пропозициональные формы (формулы логики высказываний). Считаем, что В логически следует из А, если для каждой совокупности значений пропозициональных букв, при которых А=И, форма В тоже принимает значение И. В этом случае записываем А\^В и читаем: «из А логически следует В» или «В является логическим следствием из А». Легко доказать следующую теорему. Запись \= А в логике высказываний означает, что А является тавтологией общезначимой). Докажем следующую теорему. Теорема 3.1. Если Л |=ви в |= С, тоЛ |= С. Теорема 3.2. А |=в тогда и только тогда, когда \=А^В. Доказательство. Пусть А\=В, тогда в каждой строке таблицы истинности, где А=И, будет В=И, следовательно, А^В тавтология, то есть ^^А^В. Если же имеем \=А^В, то в таблице истинности дяяА^В всюду, где Л должно быть В=И, следовательно, получимЛ \=В. Пропозициональная форма В называется логическим следствием пропозициональных форм Л;, ..., Am, т>1, если для каждой совокупности значений пропозициональных букв, при которых формы Aj, A2,..../im одновременно равны И, форма В тоже принимает значение И. В этом случае записываем: Ai ,А2,...,Ат\^В. (3.1) Выяснение, будет ли В логическим следствием из Aj, А2 Am, т>1, называют проблемой дедукции. Очевидно, что имеет место следующая теорема. Теорема 3.3. Для произвольных формул логики высказываний А1^2')---Лт, пг>1, имеют место соотношения: А]^21----Лт ^Aj&A2&...&Am, (3.2) I 60