MMW NOTES

Logic and Sets

Propositions

Proposition - a declarative sentence that can be objectively identified as either true or false

• If a proposition is true, the truth value is true represented as T or 1

• If it is not true, the truth value is false denoted as F or 0

Truth Table - given a proposition, it is a diagram in table form that is used to show all its possible truth values

Quantified statements - involve terms such as all, each, every, no , none, some, there exists, and at least one

• Universal quantifiers - all, each, every, no, none

• Existential quantifiers - some, there exists, at least one

Negation

The negation of a proposition p is the proposition which is false when p is true; and true when p is false.

• The negation of p is denoted by ¬p

Truth table

For quantified statements

Compound Propositions

Simple proposition - a proposition with only one subject and only one predicate

• Cannot be deduced to simpler propositions

• Conveys a simple idea

Compound Proposition- a proposition formed by joining two or more simple propositions with a connective

• Conveys two or more ideas

Four basic connectives

• And (conjunction)

• Or (disjunction)

• If… then (conditional)

• If and only if (biconditional)

Symbols used for the connectives

Conjunction

Let p and q be propositions.

• The conjunction of p and q is denoted by p^q , is the proposition “p and q”.

• The conjunction p^q is true only when both p and q are true, and is false otherwise

• The propositions p and q are called conjuncts

Truth table

Disjunction

Let p and q be propositions

• The disjunction of p and q is denoted by p∨q, is the proposition “p or q”

• The disjunction p∨q is false only when both p and q are false, and is true otherwise

• The propositions p and q are called dijuncts

Exclusive or

Let p and q be propositions

• The exclusive or of p and q is denoted by “p⊻q” or “p⊕q”, is the proposition that is true when exactly one of p and q is true and is false otherwise

Conditional Statements

Let p and q be propositions

• The conditional statement p→q is the proposition “if p, then q” or “p implies 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)

The Converse of p→q is q→p

The Inverse of p→q is ¬p → ¬q

The contrapositive of p→q is ¬q → ¬p

Biconditional Statements

Let p and q be propositions

• The biconditional statement p↔q, is the proposition “p if and only if q” (or simply “p iff q”)

• The biconditional statement p↔q is true only if p and q have the same truth values, and is false otherwise

• Biconditional statements are also called bi-implications

Remarks

1. If a compound statement is written in english, then a comma is used to indicate which simple statements are grouped together. Statement on the same side of the comma are grouped together

2. If a compound statement is written in symbols and there are parentheses, we find the truth value of the statement/s in the parentheses first

3. If a compound statement is written in symbols and there are no parentheses, the hierarchy of connectives would be ¬, ∧ or ∨, →, ↔. However, when a compound statement has both a conjunction and a disjunction, we need to use parentheses in order to determine which to consider first

Tautology and Contradiction

Tautology - a compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it.

Contradiction - a compound proposition that is always false

Logically implies, logically equivalent, and contingency

Let p and q be propositions (possibly compound)

• We say that p logically implies q, expressed as p =⇒ q, if the conditional statement p → q is a tautology

• If p =⇒ q and q=⇒ p, we say that p and q are logically equivalent and we write p ⇐⇒ q.

Contingency - a compound proposition that is neither a tautology nor a contradiction

* the implication p =⇒ (p ∨ q) is called the law of addition

* the implication (p ∧ q) =⇒ p is the law of simplification

Most common equivalences in logic

Theorem

Let p, q, and r be propositions

1. p ⇐⇒ q if and only if p↔q is a tautology

2. p ⇐⇒ p.

3. p ∨ q ⇐⇒ q ∨ p and p ∧ q ⇐⇒ q ∧ p. (commutative properties)

4. p ∨ (q ∨ r) ⇐⇒ (p ∨ q) ∨ r and p ∧ (q ∧ r) ⇐⇒ (p ∧ q) ∧ r. (associative properties)

5. p ∨ (q ∧ r) ⇐⇒ (p ∨ q) ∧ (p ∨ r) and p ∧ (q ∨ r) ⇐⇒ (p ∧ q) ∨ (p ∧ r). (distributive properties)

6. De Morgan’s Laws

¬(p ∨ q) ⇐⇒ (¬ p) ∧ (¬ q).

¬(p ∧ q) ⇐⇒ (¬ p) ∨ (¬ q)

1. p → q ⇐⇒ (¬ p) ∨ q.

2. ¬(p → q) ⇐⇒ p ∧ (¬ q).

3. p → q ⇐⇒ (¬ q) → (¬ p).

4. p ←→ q ⇐⇒ (p → q) ∧ (q → p).

Arguments

Argument - a compound proposition of the form (p₁∧p₂∧p₃∧· · ·∧p_n) → q.

• The propositions p₁∧p₂∧p₃∧· · ·∧p_n are the premises of the argument and q is the conclusion

• Arguments can be written in column or standard form

p1

p2

p3

:

pn

∴ q

• An argument is valid if all its premises are true implies that the conclusion is true. Otherwise, the argument is invalid

• An argument is valid if the conclusion necessarily follows from the premises, and invalid if it is not valid

• If a statement is a tautology, then the argument is valid, otherwise, the argument is invalid

Fallacy - an error in reasoning that leads to an invalid argument

Evaluating arguments with Truth Value

Procedure in determining the validity of an argument:

1. Write the arguments in symbols

2. Write the argument as a conditional statement; use a conjunctions (^) between/among the premises and the implication (→) for the conclusion

3. Set up and construct a truth table for the symbolic form

4. If all truth values under → are Ts or 1s (that is, the last column is a tautology), then the argument is valid, otherwise, it is invalid

Common forms of valid arguments

1. Law of detachment (Modus Ponens)

p → q

p

∴ q

1. Law of contraposition (Modus Tollens)

p → q

¬q

∴ ¬p

1. Law of Disjunctive Syllogism

p ∨ q

¬p

∴ q

1. Law of hypothetical syllogism (Law of Transitivity)

p → q

q → r

∴ p → r

Common Forms of Invalid Arguments

1. Fallacy of the converse

p → q

q

∴ p

1. Fallacy of the inverse

p → q

¬p

∴ ¬q

1. Fallacy of the inclusive or

p ∨ q

p

∴ ¬q

Euler Diagrams

Universal Affirmative

All a is b

Universal Negative

No a is b

Particular Affirmative

Some a is b

Particular Negative

Some a is not b

Evaluating Arguments with Euler Diagrams

To analyze an argument with an Euler diagram:

1. Draw an euler diagram based on the premises of the argument

2. The argument is valid if the diagram cannot be drawn to make the conclusion false

3. The argument is invalid if there is a way to draw the diagram that makes the conclusion false

4. If the premises are insufficient to determine the location of an element or a set mentioned in the conclusion, then the argument is invalid

Problem Solving

Reasoning - the process of drawing conclusion or inferences through the use of proper justification

Inductive Reasoning

Inductive reasoning - the process of reasoning that arrives at a general conclusion based on the observation of specific examples

specimen - object defined by a premise

Conjecture - the generalization

Counterexample - a specimen that negates the conjecture

Strong inductive argument - if it makes a compelling case for its conclusion

Weak inductive argument - if its conclusion is not well supported by the premisses

* the strength of an argument is not necessarily related with the truth of the conclusion

Deductive reasoning

Deductive reasoning - the process of reasoning that arrives at a conclusion based on previously accepted general statements

• Conclusion is based on general statements whose truth value is known or assumed.

Axioms - basic true statements

Theorems - derived true statements from axioms

Valid deductive statement - if its conclusion follows from its premises, regardless of the truth of the premises or conclusion

Sound deductive statements - if it is valid and its premises are all true

Summarization

Inductive reasoning cannot in general prove general statements as this relies on examples only. However, only one counterexample can prove our conjecture is false

We can use deductive reasoning to prove a certain conjecture

George Polya’s guidelines for problem solving

George Polya - mathematician

• Devised a model for problem solving and published it in his book How to Solve It

• The book contains a collection of mathematical and non-mathematical problems with selected strategies on dealing these

• His problem solving model which he called heuristic(or serving to discover) is as follows:

1. Understand the problem

• Ask questions, experiment, or otherwise replace the question with your own words

• Determine what is asked

• Determine the given facts

• Determine what is asked

• Determine the given condition

• Have initial illustrations to visualize the setting

• Separate various parts of the condition

1. Devise a plan

• Find the connection between the data and the unknown

• Look for patterns, relate to a previously known formula, or simplify the given information to give you an easier problem

• Choose a suitable operation, procedure or formula

1. Carry out the plan

• Check the steps as you go

• Observe the accuracy of every step

• Beware of possible errors that might arise

• Obtain a feasible solution

1. Look back

• Examine the solution obtained

• Check the sense of the solution if it is reasonable

• Check against the conditions

Along with his guidelines, the following are some of his recommended strategies:

1. Draw a diagram

2. Solve a simpler problem

3. Make a table

4. Work backwards

5. Guess and check

6. Find a pattern

7. Use a formula or an equation

8. Use logical reasoning