IMPORTANT NOTES OF LOGIC AND PROOFS (ROSEN DISCRETE MATHEMATICS)

•  A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. The area of logic that deals with propositions is called the propositional calculus or propositional logic.

•  Let p be a proposition. The negation of p, denoted by ¬p(also denoted by p'),is the statement “It is not the case that p.” The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p.

•  Let p and q be propositions. The conjunction of p and q, denoted by p∧q, is the proposition “p and q.” The conjunction p∧q is true when both p and q are  true and is false otherwise.

•  Let p and q be propositions. The disjunction of p and q, denoted by p∨q, is the proposition “p or q.” The disjunction p∨q is false when both p and q are false and is true otherwise.

•  Let p and q be propositions. The exclusive or of p and q, denoted by p⊕q, is the proposition that is true when exactly one of p and q is true and is false otherwise.

•  Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.”The conditional statement p → q is false when p is true and q is false, and true otherwise. In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).A conditional statement is also called an implication.

1.  “if p, then q” 

2. “ p implies q” 

3. “if p, q”

4. “ p only if q”

5.  “p is sufficient for q” 

6. “a sufficient condition for q is p” 

7. “q if p”

8. “ q whenever p” 

9. “q when p”

10. “ q is necessary for p” 

11. “a necessary condition for p is q”

12. “ q follows from p” 

13. “q unless ¬p” 

• .The proposition q → p is called the converse of p → q. The contrapositive of p → q is the proposition ¬q →¬p. The proposition ¬p →¬ q is called the inverse of p → q.  The contrapositive, ¬q →¬p, of a conditional statement p → q always has the same truth value as p → q. 

•  Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

1. “p is necessary and sufficient for q” 
2. “if p then q, and conversely”
3.  “p iff q.” 

• Precedence of logical operators

1.  ¬ 
2.  ∧ 
3.  ∨ 
4.  → 
5. ↔ 

• A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one). 1 represents T(true), 0 represents F(false).

• A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.

• Logical connectives are used extensively in searches of large collections of information, such as indexes of Web pages. Because these searches employ techniques from propositional logic, they are called Boolean searches. In Boolean searches, the connective AND is used to match records that contain both of two search terms, the connective OR is used to match one or both of two search terms, and the connective NOT (sometimes written as AND NOT ) is used to exclude a particular search term. Careful planning of how logical connectives are used is often required when Boolean searches are used to locate information of potential interest.

• Puzzles that can be solved using logical reasoning are known as logic puzzles.

•  A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.

• The compound propositions p and q are called logically equivalent if p ↔ q is a tautology. The notation p ≡ q denotes that p and q are logically equivalent.

1. p∧T≡ p Identity laws 
2. p∨F≡ p 
3. p∨T≡T Domination laws 
4. p∧F≡F 
5. p∨p ≡ p Idempotent laws
6.  p∧p ≡ p 
7. ¬(¬p)≡ p Double negation law
8.  p∨q ≡ q ∨p Commutative laws 
9. p∧q ≡ q ∧p
10.  (p∨q)∨r ≡ p∨(q ∨r) Associative laws 
11. (p∧q)∧r ≡ p∧(q ∧r)
12.  p∨(q ∧r)≡ (p∨q)∧(p∨r) Distributive laws 
13. p∧(q ∨r)≡ (p∧q)∨(p∧r) 
14. ¬(p∧q)≡¬p∨¬q De Morgan’s laws 
15. ¬(p∨q)≡¬p∧¬q
16.  p∨(p∧q)≡ p Absorption laws 
17. p∧(p∨q)≡ p
18.  p∨¬p ≡T Negation laws 
19. p∧¬p ≡F
20. p → q ≡¬p∨q
21.  p → q ≡¬ q →¬p 
22. p∨q ≡¬p → q
23.  p∧q ≡¬(p →¬q) 
24. ¬(p → q)≡ p∧¬q 
25. (p → q)∧(p → r)≡ p → (q ∧r) 
26. (p → r)∧(q → r)≡ (p∨q)→ r
27.  (p → q)∨(p → r)≡ p → (q ∨r)
28.  (p → r)∨(q → r)≡ (p∧q)→ r
29. p ↔ q ≡ (p → q)∧(q → p)
30.  p ↔ q ≡¬p ↔¬ q
31.  p ↔ q ≡ (p∧q)∨(¬p∧¬q)
32.  ¬(p ↔ q)≡ p ↔¬ q

• A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. a compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, that is, if and only if its negation is a tautology.  

• A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operators. 

•  The propositions p NAND q and p NOR q are denoted by p | q and p ↓ q, respectively. (The operators | and ↓ are called the Sheffer stroke and the Peirce arrow after H. M. Sheffer and C. S. Peirce, respectively.) 

•  The universal quantification of P(x)is the statement “P(x)for all values of x in the domain.” The notation ∀x P(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. We read ∀x P(x) as “for all xP(x)” or “for every x P(x).”An element for which P(x)is false is called a counterexample of ∀x P(x).

• The existential quantification of P(x)is the proposition “There exists an element x in the domain such that P(x).” We use the notation ∃x P(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.

• the uniqueness quantifier, denoted by∃!or∃1. The notation ∃!xP(x) [or ∃1xP(x)] states “There exists a unique x such that P(x)is true.” 

•  Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.

• The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus. For example, ∀x P(x)∨Q(x) is the disjunction of ∀x P(x) and Q(x). In other words, it means (∀x P(x))∨Q(x) rather than ∀x(P(x)∨Q(x)). 

• we can distribute a universal quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over a disjunction. However, we cannot distribute a universal quantifier over a disjunction, nor can we distribute an existential quantifier over a conjunction. 
• 
  
  

• 
  
  
  
  
• By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument.

•  An argument in propositional logic is a sequence of propositions. All but the final proposition in the argument are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true.

• 
  
  
  
  
  
•  Resolution is based on the tautology

                    ((p∨q)∧(¬p∨r))→ (q ∨r).

• The proposition ((p → q)∧q)→ p is not a tautology, because it is false when p is false and q is true. However, there are many incorrect arguments that treat this as a tautology. In other words, they treat the argument with premises p → q and q and conclusion p as a valid argument form, which it is not. This type of incorrect reasoning is called  the fallacy of affirming the conclusion.

• The proposition ((p → q)∧¬p)→¬ q is not a tautology, because it is false when p is false and q is true. Many incorrect arguments use this incorrectly as a rule of inference. This type of incorrect reasoning is called the fallacy of denying the hypothesis.

• Universal instantiation is the rule of inference used to conclude that P(c)is true, where c is a particular member of the domain, given the premise ∀xP(x). Universal instantiation is used when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is a member of the domain of all women.

• 
  
• 
  
  
  
  
• universal modus ponens tells us that if ∀x(P(x)→ Q(x)) is true, and if P(a)is true for a particular element a in the domain of the universal quantifier, then Q(a) must also be true.
• A direct proof of a conditional statement p → q is constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with the final step showing that q must also be true