[Discrete math] Propositional logic

Propositional Logic : 명제적 로직

from. Rosen's Discrete Mathematics

NOT : The truth table for the negation of a proposition.   

T	F
F	T

AND : The truth table for the conjunction of two propositions.

T	T	T
T	F	F
F	T	F
F	F	F

The truth table for the disjunction of two propositions.

T	T	T
T	F	T
F	T	T
F	F	F

The truth table for the exclusive or of two propositions.

T	T	F
T	F	T
F	T	T
F	F	F

inclusive or 예시 : 

"Students who have taken calculus or computer science can take this class."

미분(계산?) 또는 컴퓨터 공학 학생들은 이 수업을 들을 수 있다.  (둘 다를 듣는 학생이어도 이 수업을 들을 수 있다.)

exclusive or 예시:

"Students who have taken calculus or computer science, but not both, can enroll in this class."

미분 또는 컴퓨터 공학 학생들은 이 수업을 들을 수 있다. 그러나, 둘 다를 듣는 학생은 들을 수 없다. 

The truth table for the conditional statement p -> q.

T	T	T
T	F	F
F	T	T
F	F	T

Let p and q be propositions. The conditional statement p->q is the proposition "if p, then q"

The conditional statement p->q is false when p is true and q is false, and true otherwise.

In the conditional statement p->q, p is called the hypothesis (or antecedent or premise, implication( and q is called the conclusion (or consequence).

The statement p->q is called a conditional statement because p->q asserts that q is true on the condition that p holds.

The truth table for the conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express p->q.

The if-then construction used in many programming languages is different from that used in logic. 

Most programming languages contain statements such as if p then S, where p is a proposition and S is a program segment (one or more statements to be executed)

ex) if 2+2=4 then x := x+1

The proposition q->p is called the converse of p->q.

The contrapositive of p->q is the proposition ㄱq->ㄱp.

The proposition ㄱp->ㄱq is called the inverse of p->q. 

We will see that of these three conditional statements formed from p->q, only the contrapositive always has the same truth value as p->q.

We first show that the contrapositive, ㄱq->ㄱp, of a conditional statement p->q always has the same truth value as p->q.

To see this, note that the contrapositive is false only when ㄱp is false and ㄱq is true, that is, only when p is true and q is false.

ex) What are the contrapositive, the converse, and the inverse of the conditional statement 

"The home team wins whenever it is raining?"

solution) Because "q whenever p" is one of the ways to express the conditional statement p->q, the original statement can be rewritten as

"If it is raining, then the home team wins."

Consequently, the contrapositive of this conditional statement is 

"If the home team does not win, then it is not raining."

The converse is

"If the home team wins, then it is raining."

The inverse is

"If it is not raining, then the home team does not win."

Only the contrapositive is equivalent to the original statement.  

BICONDITIONALS 

We now introduce another way to combine propositions that expresses that two propositions have the same truth value.

Let p and q be propositions. The biconditional statement p<->q is the proposition "p if and only if q". The biconditional statement p<->q is true when p and q have the same truth values, and is false otherwise. Biconditional statement are also called bi-implications.

The truth table for the biconditional p<->q.

T	T	T
T	F	F
F	T	F
F	F	T

notations 정리

NOT, negate

AND, conjunction

OR, disjunction

IF, conditional

biconditional

XOR