귀류법(배리법)

(p → q) ⇔ (p ∧ ~q → q ∧ ~q)

​

이것을 귀류법적으로 증명해보자. 우선 위 쌍조건문에 부정을 취한다.

​

~p → ~q ⇔ (~p ∨ q) → (~q ∨ q)

​

그리고 쌍조건문의 전건에 대우를 취하고 쌍조건문의 후건인 조건문의 전건과 후건을 실질 함축 규칙을 이용하여 치환한다.

​

q → p ⇔ (p → q) → (q → q)

​

쌍조건문의 후건인 조건문의 후건은 q와 같다. p → p ≡ q

​

q → p ⇔ (p → q) → q

​

쌍조건문의 후건인 조건문을 실질 함축 규칙을 이용하여 치환하면 다음과 같다.

​

q → p ⇔ ~(p → q) ∨ q

≡ q → p ⇔ (~p → ~q) ∨ q

​

잠시 쌍조건문의 후건만 따로 떼어, 분배법칙을 이용하면 다음과 같다.

​

(~p ∨ q) → (~q ∨ q)

​

그리고 이것은 동치 규칙에 의해 다음과 같이 변환이 가능하다.

​

(~p ∨ ~q) → q

​

이것에 대우를 취하면 다음과 같다.

​

~q → ~(~p ∨ ~q)

≡ ~q → (p ∧ q)

​

이제 다시 아까의 쌍조건문의 전건을 가져와서 쌍조건문 형식으로 복원하면

​

q → p ⇔ ~q → (p ∧ q)

​

이것을 원래의 쌍조건문으로 되돌리기 위해 다시 부정을 취하면 다음과 같다.

​

~(q → p) ⇔ ~(~q → (p ∧ q))

≡ (~q → ~p) ⇔ (q → (~p ∨ ~q))

≡ p → q ⇔ q → (~p ∨ ~q)

​

이것에 실질 함축 규칙을 적용하면 다음과 같다.

​

~p ∨ q ⇔ ~q ∨(~p ∨ ~q)

​

이것은 다시 동치 규칙에 의해 다음과 같이 변환이 가능하다.

​

~p ∨ q ⇔ (~q ∨ ~p) ∨ (~q ∨ ~q)

≡ ~p ∨ q ⇔ ~p ∨ ~q

​

이것에 부정을 취해보자.

​

~(~p ∨ q) ⇔ ~(~p ∨ ~q)

≡ (p ∧ ~q) ⇔ (p ∧ q)

​

이렇게 원래의 식을 여러 규칙을 사용하여 추론한 결과, 모순이 발생함을 알 수 있다.