Propositional and First Order Logic

Question 1

Proposition

Answer 1

A declarative sentence, either true or false.

Question 2

Connectives

Answer 2

1. Negation
2. Conjunction
3. Disjunction
4. exclusive or
5. Implication
6. Bi-Implication

Question 3

Negation

Answer 3

If p is a proposition, then the negation of p is denoted by ~p( not p)

Question 4

Conjunction

Answer 4

P^Q, p and q. True when both true otherwise false.

Question 5

Disjunction.

Answer 5

P v Q, P or Q. False when both false otherwise true.

Question 6

Exclusive Or

Answer 6

P XOR Q, False when both T or F, otherwise true (for diff values)

Question 7

Implication

Answer 7

P –> Q, p: Hypothesis, Antecedent, Premise. Q : Conclusion, Consequence.
True if the premise is false and P n Q both true.
False when P is true and Q is false.

Question 8

Bi Implication.

Answer 8

P Q, P–>Q and Q –> P.

Question 9

Implication truth table confusion ka known explanation.

Answer 9

You might wonder that why is p–> q true when p is false. This is because the implication guarantees that when p and q are true then the implication is true. But the implication does not guarantee anything when the premise p is false. There is no way of knowing whether or not the implication is false since p did not happen.
This situation is similar to the “Innocent until proven Guilty” stance, which means that the implication p\rightarrow q is considered true until proven false. Since we cannot call the implication p\rightarrow q false when p is false, our only alternative is to call it true.
This follows from the Explosion Principle which says-
“A False statement implies anything”

Question 10

The question…

Answer 10

https://www.geeksforgeeks.org/gate-gate-cs-2015-set-1-question-24/

Question 11

De Morgans law

Answer 11

~( p^q) = ~p v ~q
~(p v q) = ~p ^ ~q
De Morgan’s laws extend to
¬(p1 ∨ p2 ∨ ⋯ ∨ pn) ≡ (¬p1 ∧ ¬p2 ∧ ⋯ ∧ ¬pn)
and
¬(p1 ∧ p2 ∧ ⋯ ∧ pn) ≡ (¬p1 ∨ ¬p2 ∨ ⋯ ∨ ¬pn).

Question 12

Special Conditional Statements

Answer 12

p –> q (Implication)
q –> p (Converse)
~q –> ~p (Contra+ve)
~p –> ~q (Inverse)

Question 13

Special Conditional Statements relation

Answer 13

p –> q = ~q –>~p

q –> q = ~p –> ~q

Question 14

Implicit Use of Bi Conditional

Answer 14

“If you complete your homework, then you can go out and play”. What is really meant is “You can go out and play if and only if you complete your homework”. This statement is logically equivalent to two statements, “If you complete your homework, then you can go out and play” and “You can go out and play only if you complete your homework”.

Question 15

Precedence

Answer 15

~ > “^” > “v” > “–> “ > “”

Question 16

Types of propositions based on Truth values

Answer 16

Tautology: Always True ( p v ~p )
Contradiction: Always False ( p ^ ~p)
Contingency: Nor tautology nor contradiction. (p v q)

Question 17

Identity Law

Answer 17

p ^ T = p

p v F = p

Question 18

Domination Laws

Answer 18

p ^ F = F

p v T = T

Question 19

Idempotent Laws

Answer 19

p v p = p

p ^ p = p

Question 20

Double negation Law

Answer 20

~( ~p) = p

Question 21

Commutative Law

Answer 21

p v q = q v p

p ^ q = q ^ p

Question 22

Associative Law

Answer 22

( p v q ) v r = p v ( q v r )

p ^ q ) ^ r = p ^ ( q ^ r

Question 23

Distributive Law

Answer 23

p ^ ( q v r ) = ( p ^ q ) v ( p ^ r )
p v ( q ^ r ) = ( p v q ) ^ ( p v r )

Question 24

Absorption Laws

Answer 24

p ^ ( p v q ) = p
p v ( p ^ q ) = p

Question 25

Negation laws

Answer 25

p ^ ~p = F

p V ~p = T