Discrete Mathematics Logic

Front 1

A Proposition

Back 1

a declarative sentence (a sentence that declares a fact) that is either true or false, but not both

Front 2

Propositional variables
or statement variables

Back 2

variables that represent propositions, just as letters are used to denote numerical variables

Front 3

Truth Table:
P^Q

Back 3

Only both
TFFF

Front 4

~P^Q
P^~Q

Back 4

Only one and not the other
FFTF
FTFF

Front 5

~P^~Q

Back 5

Only not one and not the other
FFFT

equivalent to ~(PvQ)

Front 6

~(P^Q)

Back 6

Not both, but anything else
FTTT

equivalent to ~Pv~Q

Front 7

PvQ

Back 7

Everything except both false
TTTF

Front 8

~PvQ
Pv~Q

Back 8

Anything except one but not the other
TFTT (equivalent to P→Q)
TTFT (equivalent to Q→P)

Front 9

~Pv~Q

Back 9

Anything except both true
FTTT

Front 10

~(PvQ)

Back 10

Not one or the other, therefore only neither
FFFT

equivalent ~P^~Q

Front 11

Truth tables and intuitive meaning
P→Q

Back 11

Anything except P=T Q=F
TFTT

Equivalent (~PvQ)
not the case of one and not the other

Front 12

Truth tables and intuitive meaning
~P→Q

Back 12

Anything except both false
TTTF
equivalent (PvQ)

Front 13

Truth tables and intuitive meaning
P→~Q

Back 13

Anything except both true
FTTT

Front 14

Truth tables and intuitive meaning
~P→~Q

Back 14

Anything except P=F and Q=T
TTFT

Front 15

Truth tables and intuitive meaning
~(P→Q)

Back 15

Only the case where P is true and Q is false
FTFF
equivalent (P^~Q)

Front 16

Equivalence
P^T
P^F

Back 16

Identity laws

P

Front 17

Equivalence
PvT
PvF

Back 17

Domination Laws
T
F

Front 18

Equivalence
PvP
P^P

Back 18

Idempotent laws

P

Front 19

Equivalence
PvQ
P^Q

Back 19

Commutative
QvP
Q^P

Front 20

Equivalence
Pv(Q^R)
P^(QvR)

Back 20

Distributive
(PvQ)^(PvR)
(P^Q)v(P^R)

Front 21

equivalence
(PvQ)^(PvR)
(P^Q)v(P^R)

Back 21

reverse of distributive law
Pv(Q^R)
P^(QvR)

Front 22

Equivalence
~(P^Q)
~(PvQ)

Back 22

De Morgan's
~Pv~Q
~P^~Q

Front 23

Equivalence
~Pv~Q
~P^~Q

Back 23

reverse of De Morgan's
~(P^Q)
~(PvQ)

Front 24

Equivalence
Pv(P^Q)
P^(PvQ)

Back 24

Absorption

P

Front 25

Equivalence
~(P→~Q)

Back 25

P^Q

Front 26

Equivalent Conditional
PvQ

Back 26

~P→Q

Front 27

Equivalence
~(P→Q)

Back 27

P^~Q

Front 28

Equivalence
(P→Q)^(P→R)

Back 28

P→(Q^R)

Front 29

Equivalence
P→(Q^R)

Back 29

(P→Q)^(P→R)

Front 30

Equivalence
(P→R)^(Q→R)

Back 30

(PvQ)→R

Front 31

Equivalence
(PvQ)→R

Back 31

(P→R)^(Q→R)

Front 32

Equivalence
(P→Q)v(P→R)

Back 32

P→(QvR)

Front 33

Equivalence
P→(QvR)

Back 33

(P→Q)v(P→R)

Front 34

Equivalence
(P→R)v(Q→R)

Back 34

(P^Q)→R

Front 35

Equivalence
(P^Q)→R

Back 35

(P→R)v(Q→R)

Front 36

Equivalence
P↔Q

Three total

Back 36

(P→Q)^(Q→P)
~P↔~Q
(P^Q)v(~P^~Q)

Front 37

Equivalence
~(P↔Q)

2 total

Back 37

P↔~Q
~(P^Q)^(PvQ)

Front 38

Inference Rule
P
P→Q

→

Back 38

Modus Ponens
Q

Front 39

Inference Rule
~Q
P→Q

→

Back 39

Modus Tollens
~P

Front 40

Inference Rule
P→Q
Q→R

→

Back 40

Hypothetical Syllogism
P→Q

Front 41

Inference Rule
PvQ
~P

→

Back 41

Disjunctive Syllogism
Q

Front 42

Inference Rule
P

→

Back 42

Addition

PvQ

Front 43

Inference Rule
P^Q

→

Back 43

Simplification

P

Front 44

Inference Rule
P
Q

→

Back 44

Conjunction
P^Q

Front 45

Inference Rule
PvQ
~PvR

→

Back 45

Resolution
QvR

Front 46

Inference Rule
∀xP(x)

→

Back 46

Universal instantiation

P(c)

Front 47

Inference Rule
P(c) for an arbitrary c

→

Back 47

Universal Generalization

∀xP(x)

Front 48

Inference Rule
∃xP(x)

→

Back 48

Exitential instantiation

P(c) for some element c

Front 49

Inference Rule
P(c) for some element c

→

Back 49

Existential generalization

∃xP(x)