동치 관계

동치-관계.pdf

0.08MB

 

#동치
:bulb: 서로 같은 진리값을 가지고 있을 때 동치라고 한다.

#### 동치 법칙

동치	이름	설명
$$1. p \wedge T \equiv p$$ $$2.p\vee F \equiv p$$	항등법칙	1. p는 항상 참 값을 가지고 있기 때문에 항상 참이다. 2. 합집합시 항상 참이 나오기 때문에 성립한다.
$$p \vee T \equiv T $$ $$ p \wedge F \equiv F$$	지배법칙	T 값에 의해 지배를 당한다고 해서 지배법칙이라고 한다. 합집합의 경우 True가 있으면 항상 참, 교집합의 경우 False가 있으면 항상 거짓
$$p \vee p \equiv p$$ $$p \wedge p \equiv p$$	멱등법칙
$$\urcorner(\urcorner p) \equiv p$$	이중부정 법칙
$$ p \vee q \equiv q \vee p$$ $$p \wedge q \equiv q \wedge p$$	교환 법칙
$$(p \vee q)\vee r \equiv p\vee(q \vee r)$$ $$(p \wedge q)\wedge r \equiv p\wedge(q \wedge r)$$	결합 법칙
$$ p\vee(q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$$ $$p \wedge(q \vee r) \equiv (p \wedge q)\vee(p \wedge r)$$	분배법칙
$$ \urcorner(p \wedge q) \equiv \urcorner p \vee \urcorner p$$ $$ \urcorner(p \vee q) \equiv \urcorner p \wedge \urcorner p$$	드 모르간의 법칙	p -> q 연산에 not을 씌우게 될 경우 이렇게 풀린다. 알아둘것,,!
$$ p \vee (p \wedge q) \equiv p$$ $$ p \wedge (p \vee q) \equiv p$$	흡수 법칙	바깥 쪽에 있는 p $\vee$ 이 부분이 굉장이 강해서 이쪽으로 흡수된다.
$$ p \vee \urcorner p \equiv T $$ $$p \wedge \urcorner p \equiv F$$	부정 법칙	둘 중 하나는 무조건 T 값을 가지기 때문에 합집합의 경우 True 둘 중 하나는 무조건 F r값을 가지기 때문에 교집합의 경우 False

:star::star: $p\rightarrow q$ 의 경우 $ \urcorner p \vee q$ 와 똑같은 의미이다.

example

1. 동치 법칙을 이용해서 $(p \rightarrow q) \wedge (p \rightarrow \urcorner q)$ 를 간소화 하여라

• 함축 법칙
  $(\urcorner p \vee q)\wedge (\urcorner p \vee \urcorner q)$
• 분배법칙
  $ \urcorner p \vee ( q \wedge q)$
• 부정법칙
  $\urcorner p \vee F$
• 항등 법칙
  $\urcorner p$
  
  
  

참고한 강의

 

마크다운 안예쁘게 나와서 pdf도 같이 올림둥