С помощью равносильных преобразований найдите формулу, равносильную данной, с указанной логической длиной l (т.е. числом вхождений в формулу пропозициональных связок):
1) ¬¬p∨p&¬q≡A∨B&C&&&&≡A∨B&(A∨C)≡¬¬p∨p&¬p∨¬q≡≡¬A∨A≡1¬A&B≡¬A∨¬B≡¬1&¬p&q≡¬¬p&q≡p&q
2) p∨q⊃p⊃r⊃¬¬r&¬q=p∨q&p⊃r⊃r∨q≡≡p∨q&¬p∨r⊃r∨q≡p&¬p∨p&r∨q&¬p∨q&r⊃r∨q≡≡¬0∨p&r∨q&¬p∨q&r∨r∨q=¬p&r&¬q&¬p&¬q&r∨r∨q≡≡¬p∨¬r&¬q∨p&¬q∨¬r∨r∨q=¬p∨¬r∨r∨q&¬q∨p∨r∨q&&¬q∨¬r∨r∨q≡1&1&1≡1≡¬p∨p
3) ¬p&¬q∨¬p&q∨p&q≡¬p&¬q∨¬p&q∨¬p&q∨p&q≡≡¬p&(¬q∨q)∨q&¬p∨p=¬p∨q
1.3.3. Выясните, имеет ли место семантическое следование:
1) p∨q⊨p&q
Решение
Формула B семантически следует из множества формул Γ, если на любом истинном наборе α для ω, на котором все формулы из Γ принимают истинные значение И, формула B также принимает значение И. Составим таблицу истинности:
p
q
p∨q
p&q
Л Л Л Л
Л И И Л
И Л И Л
И И И И
Из таблицы видно, что не для каждого набора для которого p∨q=И, p&q=И, следовательно, семантического следования нет
p∨q⊨p&q тогда и только тогда, когда ⊨(p∨q)⊃(p&q) – тавтология
p∨q⊃p&q≡¬p∨q∨p&q≡¬p&¬q∨p&q≢И
Не является тавтологией, следовательно, семантического следования нет.
2) p&q⊨p∨q
Из таблицы приведенной в п.1 видно, что для набора p&q=И имеет место p∨q=И, следовательно, семантическое следование имеет место
.
p∨q⊨p&q тогда и только тогда, когда ⊨p&q⊃p∨q – тавтология
p&q⊃p∨q≡¬p&q∨p∨q≡¬p∨¬q∨p∨q≡И
Является тавтологией, следовательно, имеет место семантического следования.
3) ¬p⊃¬q⊨p⊃q
Составим таблицу истинности:
p
q
¬p
¬q
¬p⊃¬q
p⊃q
Л Л И И И И
Л И И Л Л И
И Л Л И И Л
И И Л Л И И
Семантического следования нет, так как для набора p=И, q=Л ¬p⊃¬q=И, а p⊃q=Л.
¬p⊃¬q⊨p⊃q тогда и только тогда, когда ⊨¬p⊃¬q⊃p⊃q – тавтология
¬p⊃¬q⊃p⊃q≡¬¬¬p∨¬q∨¬p∨q≡¬p∨¬q∨¬p∨q≡≡¬p&q∨¬p∨q≡¬p∨q≢И
Не является тавтологией, следовательно, семантического следования нет.
3) p⊃q⊨¬p⊃¬q
Составим таблицу истинности:
p
q
¬p
¬q
¬p⊃¬q
p⊃q
Л Л И И И И
Л И И Л Л И
И Л Л И И Л
И И Л Л И И
семантического следования нет, так как для набора p=Л, q=И ¬p⊃¬q=Л, а p⊃q=И.
p⊃q⊨¬p⊃¬q тогда и только тогда, когда ⊨p⊃q⊃¬p⊃¬q – тавтология
p⊃q⊃¬p⊃¬q≡¬¬p∨q∨¬¬p∨¬q≡p&¬q∨p∨¬q≡≡p∨¬q≢И
Не является тавтологией, следовательно, семантического следования нет.
1.3.4