Fundamentals. Discrete Mathematics
- PDF / 2,423,229 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 294 Views
1 Fundamentals. Discrete Mathematics 1.1 Logic Statement calculus Connectives
Disjunction Biconditional Conditional Conjunction Negation
PvQ PHQ
PorQ P if and only if Q If P then Q PandQ NotP
P~Q
PI\Q -Por-,P
Truth tables (F = false, T = true)
P
Q
PvQ
PI\Q
P~Q
PHQ
T T
T
T
T
T
T
F F
F
F
F F F
F
F F
T T T
F
T T
T
P and -,P have opposite truth values.
Tautologies A tautology is true for all possible assignments of truth values to its components. A tautology is also called a universally valid formula and a logical truth. A statement formula which is false for all possible assignments of truth values to its components is called a contradiction. 9
L. Råde et al., Mathematics Handbook for Science and Engineering © Springer-Verlag Berlin Heidelberg 2004
1.1
Tautological equivalences -, -, P P PAQ QAP PvQ QvP (P A Q)AR FA (QAR) (PvQ)vR Pv(Qv R) PA(QvR) (FAQ)v(FAR) Pv(QAR) (PvQ)A(PvR) -, (P A Q) -, Pv-, Q -, (Pv Q) -, P A -, Q PvP P PAPP RV(PA -,P) R RA(PV-,P) R P ~ Q -,PvQ -,(P~ Q) PA-,Q P ~ Q (-,Q ~ -,P) P ~ (Q ~ R) «PAQ) ~ R) -, (P H Q) (P H -,Q) (P H Q) (P ~ Q)A(Q ~ P) (P H Q) (P A Q)v( -,FA -, Q)
(double negation)
(Distributive laws) (De Morgan laws)
Tautological implications ::::}
(simplification)
PAQ::::} P PAQ::::} Q P::::}PvQ Q::::}PvQ -,P::::} (P ~ Q)
(addition)
Q::::}(P~ Q) -,(P ~ Q)::::} P -,(P ~ Q)::::}-,Q -,FA(PvQ) ::::} Q PA(P ~ Q)::::} Q -, QA (P ~ Q) ::::} -,P (P ~ Q)A (Q ~ R) ::::} (P ~ R) (Pv Q)A (P ~ R)A (Q ~ R) ::::} R
T any tautology
(disjunctive syllogism) (modus ponens) (modus tollens) (hypothetical syllogism) (dilemma)
F any condradiction
Exclusive OR, NAND and NOR The connective exclusive or is denoted either P or Q, but not both are true.
"v" and is defined so that P v Q is true whenever
The connective NAND (not and) is denoted by "i" and is defined so that P
i
Q -,(P A Q)
The connective NOR (not or) is denoted by ".1," and is defined so that P .1, Q -,(P vQ)
10
1.1
Tautological equivalences PvQ QVP (PVQ)vR PV(QvR) P A (QvR) (P A Q)v(P A R) (PvQ) «PA -,Q) V(-,PAQ)) PvQ -,(PHQ) ptQQtp p!Q Q!p
Truth table
P t (Q t R) -,Pv(QAR) (P t Q) t R (P A Q)v-,R P ! (Q ! R) -,P A (QvR) (p! Q) ! R (PvQ)A-,R
P
Q PvQ ptQ p!Q
T T
T
F
F
F
F F
T
T T
F
F
T T T
F F F T
The connectives (-', A) and (-" v) can be expressed in tenus of j alone or in tenus of t alone. -,ppjp p v Q ...,pT -,Q P A Q -,(pT Q) ...,p ptp p A Q ...,p-J--,Q p v Q -,(p-J-Q) Duality Consider fonnulas containing v, A and -,. Two fonnulas A and A * are duals of each other if either one is obtained from the other by replacing A by v and vice versa.
A generalisation of De Morgan's laws: -,A (PI ' P 2' ... , P n) A*( -'pI '-,P2' ... , -,p n ). Here Pi are the atomic variables in the duals A and A *.
Normal forms If (for example) P, Q and R are statement variables, then the eight (in general 2n) fonnulas PAQAR, PAQI\-,R, PA-,QAR, PI\-,QA-,R, -,PI\QAR, -,PI\QI\-,R, -,PI\-,QI\R and -,P A-, QI\ -,R are the minterms of P, Q and R. Every statement fonnula A is equivalent to a disjunction o
Data Loading...
