Propositional Logic Exercise(logical statement, complicated statement simplifying)

 

 

 

Chapter : Propositional Logic

Topic : Logical statement, complicated statement simplifying and equivalence

 

 

 

Solution : tautology(t)가 성립한다.

1. 주어진 statemen를 simplifying했을 때 tautology가 성립하는지 판단하는 문제이다.

2. (a↔b)↔(a→b)∧(b→a)

≡ (a→b)∧(b→a)↔(a→b)∧(b→a) --- a↔b≡(a→b)∧(b→a)

≡ (~a∨b)∧(~b∨a)↔(~a∨b)∧(~b∨a) --- a→b≡(~a∨b)∧(~b∨a)

≡ (x∧y)↔(x∧y) --- x=(~a∨b) / y=(~b∨a)

≡ (x∧y→x∧y)∧(x∧y→x∧y)

≡ (x∧y→x∧y) --- p∧p≡p 임을 이용

≡ ~(x∧y)∨(x∧y) --- ~p∨p≡t

≡ tautology(t)

 

 

 

Solution : 

1. 주어진 statemen를 simplifying했을 때 equivalence가 성립하는지 판단하는 문제이다.

2. equivalence 판단은 truth table로도 가능하나, 변수가 많으면 경우의 수가 너무 많아지기 때문에 버겁다.

3. 그래서 simplifying rule을 쓰는 것이 좋다.

3. ~((a→b)∧g)∨~(d∧e∧f)∨((a∧d)→f)≡(~(a∧g∧d∧e)∧a∧~b)→~b

좌측을 먼저 풀어보면

≡ ~(~a∨b)∨~g)∨~d∨~e∨~f∨(~a∨~d)∨f --- a→b=~a∨b

≡ ~(~a∨b)∨~g∨~d∨~e∨~a∨~d∨f∨~f --- f와 ~f를 계산하기 쉽도록 자리를 이동해주었다.

≡ (~(~a∨b)∨~g∨~d∨~e∨~a∨~d)∨t --- f∨~f=t

≡ tautology(t)

우측을 풀어보면

≡ ~(~(a∧g∧d∧e)∧a∧~b)∨~b --- a→b=~a∨b임을 이용

≡ (a∧g∧d∧e)∨~a∨b∨~b --- negation분배

≡ ((a∧g∧d∧e)∨~a)∨t --- b∨~b=t

≡ tautology(t)