Навигация
В этой работе мы рассмотрим исчисление высказываний как инструмент для определения истинности утверждений. Затем мы рассмотрим расширение исчисление высказываний до исчисления предикатов. Это расширение позволит нам строить рассуждения над целым рядом конструкций таких, как циклы. Мы также рассмотрим идеи эквивалентности, общезначимости или тавтологии для доказательства.
Начало исчисления высказываний было положено работами Джоржа Буля. Подметив сходство в свойствах логических операций ОR и AND со свойствами арифметических операций умножения и сложения, он создал исчисление для вычисления истиности утверждений подобно тому, как правила арифметических операций позволяют вычислять значения арифметических выражений. В созданном им исчислении Буль обозначил символами как отдельные утверждения, так и целые конструкции из утверждений.
Любое высказывание в этом исчислении может иметь одно из двух значений: истина (true) или ложь (false). Ниже приведены примеры утверждений:
Сумма двух сторон треугольника больше или равна третьей стороне этого треугольника.
2х2=4.
“Каждый охотник желает знать, где сидят фазаны” (первые буквы слов в этой фразе определяют порядок цветов в спектре слева направо).
Для того, чтобы строго определить способ записи подобных утверждений Буль предложил понятие высказывания.
В таблице 5.1. перечислены названия и обозначения всех логических операций, используемых в высказываниях.
Таблица 5.1.
| Ø | NOT | отрицание |
| Ú | OR | дизъюнкция |
| Ù | AND | коньюнкция |
| Þ | импликация | |
| Û | тождественность |
Определение 5.1. Высказывание - выражение, построенное по следующим правилам:
true и false - высказывания;
Любая переменная типа {true, false} - высказывание (такой тип называют boolean);
Если р - высказывание, то (Øр) - высказывание;
Если p и q - высказывание, то (pÚq), (pÙq), (pÞq), (pÛq) - высказывания.
Обратите внимание на способ определения высказывания, а именно, на пункты 3 и 4 определения 5.1. Эти пункты определяют высказывание через уже существующие высказывания. С таким приемом, когда определяемое понятие определяют, используя само это понятие, мы встретимся еще не раз. Этот прием называется рекурсией.
Может возникнуть опасение “порочного круга” в таком определении. Однако, в силу пунктов 1 и 2, где понятие высказывания определяется через понятия логического значения и переменной логического типа, “зацикливания” не происходит.
Примеры 5.1.
Пусть p,q и r - переменные типа boolean.
Тогда приведенные ниже выражения - это высказывания:
| 1. | p | 6. | (pÚq) |
| 2. | q | 7. | (pÙq) |
| 3. | false | 8. | (pÞq) |
| 4. | (Øр) | 9. | (pÚ(rÙq)) |
| 5. | true | 10. | (pÞ(qÙ(rÛp)) |
То, что выражения 1,2,3,4,5 - высказывания, следует из пунктов 1,2,3 определения 5.1. Для выражений 9,10 - это следует из пунктов 2 и 4. Для выражений 9, 10 - это следует из пункта 2 и последовательного применения пункта 4 определения.
Например:
(pÞ(qÙ(rÛp))
rÞp - высказывание по пункту 4. Обозначим его s1.
(qÙs1) - высказывание опять по пункту 4. Обозначим его s2 .
(pÞs2) - высказывание по тому же самому пункту 4.
Пример 5.2. Ниже приведенные выражения не являются высказываниями.
(pq)
(pq) Øр
Выражение 1 не является таковым, потому что имена двух переменных стоят рядом и не разделены знаком логической операции.
Выражение 2 не является высказыванием, во-первых, потому, что (pq) - не высказывание; во-вторых, потому, что выражение sØр , - где s и p - высказывания, не удовлетворяет ни одному из 4-х пунктов определения 5.1.
Особое внимание следует обратить на скобки. Их можно опускать если это не вносит неоднозначности. Например, вместо (Øр) можно писать Øр, а вместо (pÚq) - pÚq. Однако, невнимательное обращение со скобками может привести к неоднозначности. Например, выражение pÚqÙr можно трактовать либо как ((pÚ)qÙr), либо (pÚ(qÙr)). Для того, чтобы избежать такой неоднозначности, пяти логическим операциям приписывается приоритет, который учитывается при вычислении значения выражения. Операция отрицания Ø - имеет наивысший приоритет, за ней следует Ù, потом следует Ú, Þ и Û в том порядке как они указаны. Поэтому, выражение pÚqÙr должно трактоваться только как (pÚ(qÙr)).
Похожие работы
... , которые используются при доказательстве теорем вручную, системы автоматического доказательства для фразовых форм используют единственное правило вывода — принцип резолюций, — впервые описанное Робинсоном ([Robinson, 1965]). Рассмотрим следующий пример из исчисления высказываний. В дальнейшем прописными буквами Р, Q, R,... будут обозначаться отдельные фразы, а строчными греческими U, ф и £ ...
... р {Допущение} 2) рÚ F(х) {ВД: 1} "х рÚ F(х) {В": 2} Докажем теперь формулу (38): "х F(х) ®$х F(х) Доказательство: 1) "х F(х) {Допущение} 2) F(у) {У": 1} $х F(х) {В$: 2} 5. ПОГРУЖЕНИЕ АРИСТОТЕЛЕВСКОЙ СИЛЛОГИСТИКИ В УЗКОЕ ИСЧИСЛЕНИЕ ПРЕДИКАТОВ В логике Аристотеля и его последователей вплоть до конца ХІХ столетия основная роль приписывалась четырем видам ...
... ; В) — при любой расстановке скобок в конъюнкции согласно правилам построения формул. В связи с отмеченной неразрешимостью логики предикатов особое значение приобретает здесь формализация понятий следования и закона логики посредством построения логических исчислений. Именно исчисление дает возможность во многих случаях синтаксическим образом решать вопрос, является ли некоторая формула законом, ...
... нормальная форма какой-то формулы. Она удовлетворяет условиям: a) в ней нет двух одинаковых конъюнкций; b) ни одна конъюнкция не содержит двух одинаковых дизъюнкций; c) ни одна конъюнкция не содержит переменного высказывания вместе со свои отрицанием; d) в каждой конъюнкции содержится в качестве дизъюнктивных членов все переменные входящие в формулу. Правила приведения пр
0 комментариев