Discrete_Mathematics Ch1

Propositional Logic, Predicates, Quantifier, Rules of Inference, Proof에 관하여 학습한다.

Logic

Proposition

Proposition(명제)는 참과 거짓을 명확히 가릴 수 있는 문장을 뜻한다.
논리연산자를 이용하여 복합 명제를 만들 수 있다.

논리연산은 컴퓨터에서 참을 1로, 거짓을 0으로 표현한다.

p / q	Conjunction (\(p \wedge q\))	Disjunction (\(p \vee q\))	Negation (\(\neg p\))	Exclusive OR (\(p \oplus q\))	Implication (\(p \rightarrow q\))	Biconditional (\(p \leftrightarrow q\))
T / T	T	T	F	F	T	T
T / F	F	T	F	T	F	F
F / T	F	T	T	T	T	F
F / F	F	F	T	F	T	T

Logical Equivalence

두 명제의 진리값이 모두 동일할 때, 이를 두 명제가 논리적으로 동등하다(Equivalance) 라고 표현한다.

Equivalence	Equivalence	Equivalence	Equivalence
\(p \wedge T \equiv p\) \(p \vee F \equiv p\)	\(p\vee q \equiv q \vee p\) \(p\wedge q\equiv q \wedge p\)	\(p \rightarrow q\) \(\equiv \neg p \vee q\)	\((p \rightarrow q) \wedge (p \rightarrow r)\) \(\equiv p\rightarrow (q \wedge r)\)
\(p \vee p \equiv p\) \(p \wedge p \equiv p\)	\(p\vee (p \wedge q) \equiv p\) \(p\wedge(p\vee q)\equiv p\)	\(p \rightarrow q\) \(\equiv \neg q \rightarrow \neg p\)	\((p \rightarrow r) \wedge (q \rightarrow r)\) \(\equiv (p \vee q)\rightarrow r\)
\(p \vee T \equiv T\) \(p \wedge F \equiv F\)	\((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\) \(\equiv \neg p \rightarrow q\)	\(p \leftrightarrow q\) \(\equiv (p\rightarrow q) \wedge (q \rightarrow p)\)
\(p \vee \neg p \equiv T\) \(p \wedge \neg p \equiv F\)	\(\neg(p\wedge q) \equiv \neg p \vee \neg q\) \(\neg(p\vee q) \equiv \neg p \wedge \neg q\)	\(p \wedge q\) \(\equiv \neg (p \rightarrow \neg q)\)	\(\neg (p \leftrightarrow q)\) \(\equiv p \leftrightarrow \neg q\)
\(\neg(\neg p) \equiv p\)	\(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)\)	\(\neg (p \rightarrow q)\) \(\equiv p \wedge \neg q\)	\(p \leftrightarrow q\) \(\equiv \neg p \leftrightarrow \neg q\) \(\equiv (p \wedge q) \vee (\neg p \wedge \neg q)\)

복합명제의 진리값이 참이 되는 경우가 있다면 Satisfiable, 그렇지 않다면 Unsatisfiable로 표현한다.

Predicates and Quantifier

변수의 값에 따라 진리치가 변하는 문장을 조건문(Predicate)이라 하고, 해당 변수의 범위를 지칭하는 기호를 양화사(Quantifier)라고 한다.

Example 1: 모든 x에 대하여 \(x^2 \geq 0\) 이다
\(\equiv \forall x (x^2 \geq 0)\)
Example 2: 어떤 y에 대하여 \(y > 21\) 이다
\(\equiv \exists y (y > 21)\)

조건문에 속해있는 모든 변수는 범위가 한정되어 있어야 한다

양화사가 포함된 조건문의 부정은 다음과 같이 처리한다

Negation	Equiv statement	When Negation True?	When False?
\(\neg \exists xP(x)\)	\(\forall x \neg P(x)\)	For every \(x\), \(P(x)\) is false.	There is an \(x\) for which \(P(x)\) is true
\(\neg \forall xP(x)\)	\(\exists x \neg P(x)\)	There is an \(x\) for which \(P(x)\) is false.	\(P(x)\) is true for every \(x\)

양화사의 중첩은 다음과 같이 처리한다.

Statement	When True?	When False?
\(\forall x \forall yP(x,y)\)	\(P(x,y)\) is true for every pair \(x, y\).	There is a pair \(x,y\) for which \(P(x,y)\) is false.
\(\forall x \exists yP(x,y)\)	For every \(x\) there is a \(y\) for which \(P(x,y)\) is true.	There is an \(x\) such that \(P(x,y)\) is false for every \(y\)
\(\exists x \forall yP(x,y)\)	There is an \(x\) for which \(P(x,y)\) is true for every \(y\).	For every \(x\) there is a \(y\) for which \(P(x,y)\) is false
\(\exists x \exists yP(x,y)\)	There is a pair \(x,y\) for which \(P(x,y)\) is true.	\(P(x,y)\) is false for every pair \(x, y\).

Rules of Inference

추론 규칙(Rules of Inference)는 주어진 전제로부터 논리적으로 유효한 결론을 도출하는 기법이다.

전제들이 항상 참임을 가정하고 시행하는 규칙임을 잊지말자, 전제가 거짓이면 사용에 의미가 없다.

Tautology	Rule of Inference	Tautology	Rule of Inference
\(\begin{align}&(p\wedge (p \rightarrow q)) \\&\rightarrow q\end{align}\)	\(\begin{align}&p\\&\underline{p\rightarrow q}\\\therefore &\,q\end{align}\)	\(\begin{align}&(\neg q \wedge(p \rightarrow q)) \\&\rightarrow \neg p\end{align}\)	\(\begin{align}&\neg q\\&\underline{p\rightarrow q}\\\therefore &\,\neg p\end{align}\)
\(\begin{align}&((p\vee q) \wedge \neg p) \\&\rightarrow q\end{align}\)	\(\begin{align}&p \vee q\\&\underline{\neg p\,\,\,\,\,\,\,}\\\therefore &\,q\end{align}\)	\(\begin{align}&((p\rightarrow q) \wedge (q \rightarrow r)) \\&\rightarrow (p \rightarrow r)\end{align}\)	\(\begin{align}&p\rightarrow q\\&\underline{q\rightarrow r}\\\therefore &\,p \rightarrow r\end{align}\)
\(p \rightarrow (p \vee q)\)	\(\begin{align}&\underline{p\,\,\,\,\,\,\,\,\,\,}\\\therefore & \,p\vee q\end{align}\)	\((p \wedge q) \rightarrow p\)	\(\begin{align}&\underline{p \wedge q}\\\therefore & \,p\end{align}\)
\(\begin{align}&((p) \wedge (q)) \\&\rightarrow (p \wedge q)\end{align}\)	\(\begin{align}&p\\&\underline{q\,\,\,\,\,\,\,\,}\\\therefore &\,p \wedge q\end{align}\)	\(\begin{align}&((p \vee q) \wedge (\neg p \vee r))\\&\rightarrow (q \vee r)\end{align}\)	\(\begin{align}&p \vee q\\&\underline{\neg p \vee r}\\\therefore &\,q \vee r\end{align}\)