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

истинна, а В ложна. Если W имеет вид Av В, то надо найти значения переменных, при которых обе формулы А я В ложны. Если W имеет вид А&В, то надо найти или значения переменных, при которых А ложна, или значения переменных, при которых В ложна. Тем самым задача поиска контрпримера для формулы W сводится к одной или нескольким аналогичным задачам. Введём необходимую терминологию и обозначения. Будем называть секвенцией выражение Г ^ Л, где Г я Л — некоторые конечные множества формул, знак ^ разделяет эти множества формул. С каждой секвенцией Г ^ Л будем связывать задачу поиска таких значений переменных, при которых все формулы из Г истинны, а все формулы из А ложны. Такой набор значений будем называть контрпримером к секвенции Г ^ Л. Пусть Г = {Ai, А2,...А„}, а = {Bi, B2,...Bfn}. Легко проверить, что контрпримеры к секвенции Г ^ Л — это контрпримеры к формуле W = Ai8cA2&. . ЛАп ^ Si V ^2 V.. .V В^. то есть те наборы значений, при которых формула W ложна. При этом конъюнкцию пустого множества формул считаем тождественно истинной, а дизъюнкцию пустого множества формул считаем тождественно ложной. Теперь задача поиска контрпримера, например, к формуле В может быть сформулирована как задача поиска контрпримера к секвенции: 0 ^ {В]. В дальнейшем вместо 0 ^ {5} для краткости будем записывать ^ В, а вместо {А} ^ 0 будем записывать А^ Пусть в левой и правой частях секвенции встречаются одинаковые выражения, например, формула D содержится и слева и справа секвенции. Тогда в формуле W будет содержаться —DvD поэтому W является тавтологией и не может быть ложной, и, следовательно, W не имеет контрпримера. Например, секвенция А А,В не имеет контрпримера, так как формула W= A^AvB ~ —AvAvB является тавтологией. Секвенция А ^ В, С имеет контрпример, так как формула W=A^BvC AvBvC будет ложна, когда ^ = И, В=С=Л. § 18. Задание исчисления высказываний в виде исчисления секвенций 131