Propositional logic Flashcards
Types of logic
Propositional logic
Predicate or first order logic
Propositional logic (definition)
A propositional logic is a declarative statement.
It must be either TRUE or FALSE.
It cannot be both TRUE and FALSE.
Choose if following are proposition or not
a.) John loves CSE 191
b.) 2+3
c.) 2+x=3
d.) 2+x>3
e.) sun rises from west
a.) John loves CSE 191- Proposition
b.) 2+3 - Non proposition
c.) Solve 2+x=3 - Non proposition
d.) 2+x>3 - non proposition
e.) sun rises from west - Proposition
Another name of propositional logic
Boolean logic
Tautology
A propositional formula which is always true
Contradiction
A propositional which is always failed
Valid sentence
Tautology
Statements which are ______________ are not propositions.
Statements which are questions, commands, or opinions are not propositions.
Connectives
Connectives can be said as logical operator which connects two sentences.
Types of propositions
Two types of propositions:
1.) Atomic propositions
2.) Compound propositions
Atomic propositions
(Also example)
Atomic propositions are the simple propositions that consist of a single proposition symbol. These are the sentences which must be either true or false.
Ex: Today is monday
Compound propositions
(Also example)
Compound propositions are constructed by combining simpler or atomic propositions, using parentheses and logical connectives.
Ex: Today is Monday and I am going to Goa.
Operators (5)
¬ negation
^ and
v or
→implication
⟺ bidirectional implication
Negation ¬
* Definition
* Example
* Unitary/binary
* generate new proposition or not
* Truth table
Suppose p is proposition
The negation of p is ¬p
ex- p: Today is Monday
¬p: Today is not Monday
Unitary
Generate new proposition
And
* symbol
* another name
* unary/binary
* truth table
Conjuction
binary
Disjuction
* Type
About each type:
* symbol
* unary/binary
* truth table
Type: Inclusive or and exclusive or
Inclusive OR
* v
* binary
Exclusive OR (XOR)
* ⊕ or ⊻
* binary
⊕ expressed other operators
p⊕q is same as ¬(p⟺q)
→
* name
* truth table
* what is p and q in p→q
→
* implication
* p is antecedant and q is consequent in p→q
Terminology for implication (7)
p→q
* if p, then q
* q, if p
* p, only if q
* p implies q
* p is sufficient for q
* q is necessary for p
* q follows from p
p→q equivalent to (2)
p→q = ¬pvq
p→q = ¬q→¬p
⟺
* name
* unary/binary operator
* keyword
* p⟺q same as ?
* truth table
* how to remember truth table
⟺
* bidirectional implication
* binary operator
* keyword: if only if
* p⟺q same as p→q and q→p taken together.
* same:True
precedence of operators
type of formulas in propositional logic
Logical consequence
A formula ϕ is said to be logical consequence of another formula ψ if whenever ψ is True, ϕ must also be True.
This means the truth of ψ guarantees the truth of ϕ symolically, ψ ⊨ ϕ
De Morgan law (propositional logic)
Distributivity (propositional logic)
Contrapositives (propositional logic)
Identity law (propositional logic)
Domination laws (propositional logic)
Idempotent laws
Double negation laws
Commutative laws
Associative laws
Absorption laws
Negation laws
Logical equivalences involving biconditional statements
Number of propositional models
Number of propositional models = 2ⁿᵘᵐᵇᵉʳ ᵒᶠ ᵖʳᵒᵖᵒˢᶦᵗᶦᵒⁿˢ
[2^(number of propositions)]
Entailment
α ⊨β (alpha entails beta)
In every model in which sentence α is true, sentence β is also true.
entailment is not proposition but it is relation
Model checking
Model checking is not an efficient algorithm because_____
Model checking is not an efficient algorithm because it has to consider every possible model before giving the answer.
Inference in propositional logic
Inference rules allow us to generate new information based on existing knowledge without considering every possible model.
Inference is the process of deriving new sentences from old ones.
Inference rules are represented as
What is premise and conclusion in inference rules
The premise is whatever the knowledge we have, and the conclusion is what knowledge can be generated based on the premise.
Modus ponens
And elimination
Double negation elimination
Implication elimination
Biconditional elimination
De Morgans law as inference
Distributive property as inference
Resolution as inference
