The foundations: logic and proof Flashcards
Atomic proposition
Propositions that cannot be expressed in terms of simpler propositions
compound propositions
compound propositions are formed
from existing propositions using logical operators.
Conditional, contrapositive, inverse, converse.
Conditional and Contrapositive are equivalent.
converse and inverse are equivalent ( as the inverse is converse’s contrapositive)
Some forms of saying if p then q?
14
- “if p, then q” 3. “p implies q”
- “if p, q” 4. “p only if q”
- “p is sufficient for q”
- “a sufficient condition for q is p”
- “q IF p”
- “q WHENEVER p”
- “q WHEN p”
- “q is NECESSARY for p”
- “a necessary condition for p is q”
- “q FOLLOWS from p”
- “q UNLESS ¬p”
- “q PROVIDED that p”
Some ways of saying p if and only if q ( bi implication)?
4
“p is necessary and sufficient for q”
“if p then q, and conversely”
“p iff q.” “p exactly when q.”
Precedence.
It is generally the case that unary operators that involve only one object precede binary operators.
z whenever o is
if o then z; o –> z
a is sufficient for v
a–>v ; if a then v
f is necessary for g
if g then f; g –> f
Application of propositional logic.
- System specifications
- Boolean search
- logic puzzle
- logic circuits
System specifications
System specifications
should be consistent, that is, they should not contain conflicting requirements that could be used to derive a contradiction.
When specifications are not consistent,
there would be no way to develop a system that satisfies all specifications
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.
logically equivalent
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.
≡ : not a logical connective.
p ≡ q: not a compound proposition but a statement meaning ‘p ↔ q is a tautology’.
conditional disjunction equivalence.
p → q ≡ ¬p ∨ q
Logical Equivalences
Involving Conditional
Statements. 2 variables. (5)
p → q ≡ ¬p ∨ q p → q ≡ ¬q → ¬p p ∨ q ≡ ¬p → q p ∧ q ≡ ¬(p → ¬q) ¬(p → q) ≡ p ∧ ¬q
Logical Equivalences
Involving Conditional
Statements. 3 variables. (4)
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
Logical
Equivalences Involving
Biconditional Statements (4)
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p↔ q) ≡ p ↔ ¬q
De Morgan’s law extended:
Furthermore, note that De Morgan’s laws extend to
¬(p1 ∨ p2 ∨ ⋯ ∨ pn) ≡ (¬p1 ∧ ¬p2 ∧ ⋯ ∧ ¬pn)
and
¬(p1 ∧ p2 ∧ ⋯ ∧ pn) ≡ (¬p1 ∨ ¬p2 ∨ ⋯ ∨ ¬pn)
When using De
Morgan’s laws,
remember to
change
the logical connective
after you negate.
Satisfiability :
A compound proposition is satisfiable if there is an assignment of truth values to its variables
that makes it true (i.e, when it is a tautology or a contingency).
unsatisfiable:
when the compound proposition is false for all assignments of truth values to
its variables.
Note that a compound proposition is
unsatisfiable if and only if its negation is true for all assignments of truth values to the variables,
i.e, if and only if its negation is a tautology.
The solution to a satisfiable problem:
When we find a particular assignment of truth values that makes a compound proposition
true, we have shown that it is satisfiable; such an assignment is called a solution to this particular
satisfiability problem.
Predicate
predicate,
ex: “is greater than 3”
—refers to a property that
the subject of the statement can have
P(x), what do you understand from this?
The statement P(x) is also
said to be the value of the propositional function P at x. Once a value has been assigned to the
variable x, the statement P(x) becomes a proposition and has a truth value.
“x = y + 3.” denoted by Q(x, y), where x and y are variables, and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value.
Propositional functions
In general, a statement involving the n variables x1, x2, … , xn can be denoted by
P(x1, x2, … , xn).
A statement of the form P(x1, x2, … , xn) is the value of the propositional function P at the
n-tuple (x1, x2, … , xn), and P is also called an n-place predicate or an n-ary predicate.
Propositional functions occur in computer programs like
if x > 0 then x := x + 1
Preconditions and Postconditions
The statements that describe valid
input are known as preconditions and the conditions that the output should satisfy when the
program has run are known as postconditions.
Predicate Calculus
The area of logic that deals with predicates
and quantifiers is called the predicate calculus.
Quantification
Quantification expresses
the extent to which a predicate is true over a range of elements.
Domain
domain
specifies the possible values of the variable x for P(x).
The universal quantification of P(x) is the statement:
The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the
universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x).”
CounterExample:
An element for which P(x) is false is called a counterexample to ∀xP(x).
The domain of Discourse:
Many mathematical statements assert that a property is Assessment true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain
universal quantification can be expressed in many other
- “for all”
- “for every,”
- “all of,”
- “for each,”
- “given any,”
- “for arbitrary,”
- “for each,”
- “for any.” – avoid use, ‘any’ is ambiguous unless its negatives we talking bout.
The existential quantification of P(x) is the proposition
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 ∃xP(x) for the existential quantification of P(x). Here ∃ is called the
existential quantifier.
express existential quantification:
∃xP(x)
- “there exists,”
- “for some,”
- “for at least one,”
- “there is.”
- “There is an x such that P(x),”
- “There is at least one x such that P(x),”
- “For some xP(x).”
Uniqueness Quantifier
denoted by ∃! or ∃1. The notation ∃!xP(x) [or ∃1xP(x)] states 1. “There exists a unique x such that P(x) is true.” 2.“there is exactly one” 3.“there is one and only one.”
the universal quantification ∀xP(x) is the
same as?
the universal quantification ∀xP(x) is the
same as the conjunction
P(x1) ∧ P(x2) ∧ ⋯ ∧ P(xn),
because this conjunction is true if and only if P(x1), P(x2), … , P(xn) are all true.
[ when the elements of the
domain are x1, x2, …, xn, where n is a positive integer ]
existential quantification ∃xP(x) is the same as?
existential quantification ∃xP(x) is the same as the disjunction
P(x1) ∨ P(x2) ∨ ⋯ ∨ P(xn),
because this disjunction is true if and only if at least one of P(x1), P(x2), … , P(xn) is true.
[ when the elements of the
domain are x1, x2, …, xn, where n is a positive integer ]
CONNECTIONS BETWEEN QUANTIFICATION AND LOOPING?
We can loop through the domain elements to check the truth value of quantifiers. For universal quantifier, if there is no element for which the p(x) is false then its true. For existential quantifier if there is an element for which P(x) is true then it’s true and if no element satisfies then its false.
restriction of a universal quantification
Note that the restriction of universal quantification is the same as the universal quantification of a conditional statement. For instance, ∀x < 0 (x raise to 2 > 0) is another way of expressing
∀x(x < 0 → x raise to 2 > 0).
restriction of an existential quantification
The restriction of an existential quantification is the
same as the existential quantification of conjunction. For instance, ∃z > 0 (z raise to 2 = 2) is another
way of expressing ∃z(z > 0 ∧ z raise to 2 = 2).
Precedence Of quantifiers:
Universal and existential quantifiers come before logical operators.
∀xP(x) ∨ Q(x) is (∀xP(x)) ∨ Q(x) not ∀x(P(x) ∨ Q(x)).
When is a variable bound and when is it free?
When a quantifier is used on the variable x, we say that this occurrence of the variable is bound otherwise it is free.
Scope of quantifier?
Variable outside this scope is?
Usage of same letters as variables:
The part of a logical expression to which a quantifier is applied is called the scope of this
quantifier.
Consequently, a variable is free if it is outside the scope of all quantifiers in the formula that specify this variable.
So, the same letter is often used to represent variables bound by different quantifiers with scopes that do not
overlap.
Negation of quantified expression:
¬∀xP(x) ≡ ∃x ¬P(x)
¬∃xP(x) ≡ ∀x¬P(x)
Fuzzy logic
0 : False
1 : True
Fuzzy logic is used in artificial intelligence. In fuzzy logic, a proposition has a truth value that is a number between 0 and 1, inclusive
Truth values that are between 0 and 1 indicate varying degrees of truth.
Order of nested Quantifier:
The order doesn’t matter if its just universal quantifier or just existential. When using different quantifiers matters.
Negation in fuzzy logic.
The truth value of the negation of a proposition in fuzzy logic is 1 minus the truth value of the proposition
Conjunction in fuzzy logic.
The truth value of the conjunction of two propositions in fuzzy logic is the minimum of the truth values of the two propositions.
Disjunction in fuzzy logic.
Maximum one.
Dual of a proposition
The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound proposition obtained by replacing each ∨ by ∧, each ∧ by ∨, each T by F, and each F by T. The dual of s is denoted by s∗.
Disjunctive Normal
Suppose that a truth table in n propositional variables is specified. Show that a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is true. The resulting compound proposition is said to be in disjunctive normal form.
functionally complete
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.
NAND
logical operators NAND. The proposition p NAND q is true when either p or q, or both, are false; and it is false when both p and q are true. p ∣ q ¬(p ^ q) | aka Sheffer stroke. [ H. M. Sheffer ]
NOR
The proposition p NOR q is true when both
p and q are false, and it is false otherwise.
p ↓ q
¬(p ∨ q)
↓ aka Peirce arrow [ C. S. Peirce ]
represent ↓ and negations relation
p ↓ p = ¬p
represent or using only nor
(p ↓ q) ↓ (p ↓ q ) = p v q
Null quantification:
establish rules for null quantification that
we can use when a quantified variable does not appear in part of a statement.
a) (∀xP(x)) ∨ A ≡ ∀x(P(x) ∨ A)
b) (∃xP(x)) ∨ A ≡ ∃x(P(x) ∨ A)
a) (∀xP(x)) ∧ A ≡ ∀x(P(x) ∧ A)
b) (∃xP(x)) ∧ A ≡ ∃x(P(x) ∧ A)
a) ∀x(A → P(x)) ≡ A → ∀xP(x)
b) ∃x(A → P(x)) ≡ A → ∃xP(x)
a) ∀x(P(x) → A) ≡ ∃xP(x) → A
b) ∃x(P(x) → A) ≡ ∀xP(x) → A
