Propositional logic

Question 1

Types of logic

Answer 1

Propositional logic
Predicate or first order logic

Question 2

Propositional logic (definition)

Answer 2

A propositional logic is a declarative statement.
It must be either TRUE or FALSE.
It cannot be both TRUE and FALSE.

Question 3

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

Answer 3

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

Question 4

Another name of propositional logic

Answer 4

Boolean logic

Question 5

Tautology

Answer 5

A propositional formula which is always true

Question 6

Contradiction

Answer 6

A propositional which is always failed

Question 7

Valid sentence

Answer 7

Tautology

Question 8

Statements which are ______________ are not propositions.

Answer 8

Statements which are questions, commands, or opinions are not propositions.

Question 9

Connectives

Answer 9

Connectives can be said as logical operator which connects two sentences.

Question 10

Types of propositions

Answer 10

Two types of propositions:
1.) Atomic propositions
2.) Compound propositions

Question 11

Atomic propositions
(Also example)

Answer 11

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

Question 12

Compound propositions
(Also example)

Answer 12

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.

Question 13

Operators (5)

Answer 13

¬ negation
^ and
v or
→implication
⟺ bidirectional implication

Question 14

Negation ¬
* Definition
* Example
* Unitary/binary
* generate new proposition or not
* Truth table

Answer 14

Suppose p is proposition
The negation of p is ¬p

ex- p: Today is Monday
¬p: Today is not Monday

Unitary

Generate new proposition

Question 15

And
* symbol
* another name
* unary/binary
* truth table

Answer 15

Conjuction
binary

Question 16

Disjuction
* Type

About each type:
* symbol
* unary/binary
* truth table

Answer 16

Type: Inclusive or and exclusive or

Inclusive OR
* v
* binary

Exclusive OR (XOR)
* ⊕ or ⊻
* binary

Question 17

⊕ expressed other operators

Answer 17

p⊕q is same as ¬(p⟺q)

Question 18

→
* name
* truth table
* what is p and q in p→q

Answer 18

→
* implication
* p is antecedant and q is consequent in p→q

Question 19

Terminology for implication (7)

Answer 19

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

Question 20

p→q equivalent to (2)

Answer 20

p→q = ¬pvq
p→q = ¬q→¬p

Question 21

⟺
* name
* unary/binary operator
* keyword
* p⟺q same as ?
* truth table
* how to remember truth table

Answer 21

⟺
* bidirectional implication
* binary operator
* keyword: if only if
* p⟺q same as p→q and q→p taken together.
* same:True

Question 22

precedence of operators

Answer 22

Question 23

type of formulas in propositional logic

Answer 23

Question 24

Logical consequence

Answer 24

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, ψ ⊨ ϕ

Question 25

De Morgan law (propositional logic)

Answer 25

Question 26

Distributivity (propositional logic)

Answer 26

Question 27

Contrapositives (propositional logic)

Answer 27

Question 28

Identity law (propositional logic)

Question 29

Domination laws (propositional logic)

Question 30

Idempotent laws

Question 31

Double negation laws

Question 32

Commutative laws

Question 33

Associative laws

Question 34

Absorption laws

Question 35

Negation laws

Question 36

Logical equivalences involving biconditional statements

Question 37

Number of propositional models

Answer 37

Number of propositional models = 2ⁿᵘᵐᵇᵉʳ ᵒᶠ ᵖʳᵒᵖᵒˢᶦᵗᶦᵒⁿˢ

[2^(number of propositions)]

Question 38

Entailment

Answer 38

α ⊨β (alpha entails beta)
In every model in which sentence α is true, sentence β is also true.
entailment is not proposition but it is relation

Question 39

Model checking

Question 40

Model checking is not an efficient algorithm because_____

Answer 40

Model checking is not an efficient algorithm because it has to consider every possible model before giving the answer.

Question 41

Inference in propositional logic

Answer 41

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.

Question 42

Inference rules are represented as

Answer 42

Question 43

What is premise and conclusion in inference rules

Answer 43

The premise is whatever the knowledge we have, and the conclusion is what knowledge can be generated based on the premise.

Question 44

Modus ponens

Question 45

And elimination

Question 46

Double negation elimination

Question 47

Implication elimination

Question 48

Biconditional elimination

Question 49

De Morgans law as inference

Question 50

Distributive property as inference

Question 51

Resolution as inference