1 - Introduction to logic and impossibility. Mathematical Implication. Truth tables Flashcards
What is a proposition?
A proposition is a statement that can be either true or false. It is objective.
2+2=4 and 2+2=5 are propositions
“Sydney is in Australia” and “I love ice cream” are not. Context matters, they are subjective.
What does a contrapositive statement mean?
A proposition or theorem formed by contradicting both the subject and predicate or both the hypothesis and conclusion of a given proposition or theorem and interchanging them “if not-B then not-A “ is the contrapositive of “if A then B”
E.g. For the statement “If the sun is shining we are heading off to the surf”, the contrapositive statement would be “If we are not heading to the surf then the sun is not shining.”
It swaps the order and changes the “sign” of the statement.
What is a proof?
A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion.
What is a converse statement?
The converse of a statement is formed by switching the hypothesis and the conclusion. The converse of “If two lines don’t intersect, then they are parallel” is “If two lines are parallel, then they don’t intersect.” The converse of “if p, then q” is “if q, then p.”
E.g. For the statement “If the sun is shining we are heading off to the surf”, the converse statement would be “If we are heading off to the surf then the sun is shining.”
What is propositional logic?
Some sets of propositions can logically imply a new proposition.
E.g. Given two statements:
“Sydney is in NSW” and “NSW is in Australia”
You can deduce that “Sydney is in Australia”
What is logical negation?
The negation of a statement is also a statement with a truth value that is exactly the opposite that of the original statement. For instance, the negation of the statement is written symbolically as
~P or ¬P.
~P or ¬P is read as “not P.”
What is logical conjunction?
A conjunction is a type of compound statement that is comprised of two propositions (also known as simple statements) joined by the AND operator.
The symbol that is used to represent the AND or logical conjunction operator is ∧. It looks like an inverted letter V.
If we have two simple statements P and Q, and we want to form a compound statement joined by the AND operator, we can write it as:
P∧Q
P∧Q is read as “P and Q.”
What is logical disjunction?
A disjunction is a kind of compound statement that is composed of two simple statements formed by joining the statements with the OR operator.
In a disjunction statement, the use of OR is inclusive. That means “one or the other” or both.
The symbol that is used to represent the OR or logical disjunction operator is ∨. It resembles the letter V of the alphabet.
Two propositions P and Q joined by OR operator to form a compound statement is written as:
P∨Q
P∨Q is read as “P or Q.”
What is logical implication?
An implication (also known as a conditional statement) is a type of compound statement that is formed by joining two simple statements with the logical implication connective or operator.
The symbol that is used to represent the logical implication operator is an arrow pointing to the right, thus a rightward arrow.
A rightward arrow is used to denote a conditional statement P → Q
When two simple statements P and Q are joined by the implication operator, we have:
P→Q.
where P is known as the hypothesis
where Q is known as the conclusion
There are many ways how to read the conditional P→Q. Below are some of the few common ones:
P→Q is read as “P implies Q“.
P→Q is read as “If P then Q“.
P→Q is read as “P only if Q“.
P→Q is read as “If P is sufficient for Q“.
P→Q is read as “Q is necessary for P“.
P→Q is read as “Q follows from P“.
P→Q is read as “Q if P“.
What is logical biconditional or Double implication?
A double implication (also known as a biconditional statement) is a type of compound statement that is formed by joining two simple statements with the biconditional operator. A biconditional statement is really a combination of a conditional statement and its converse.
The biconditional operator is denoted by a double-headed arrow.
A double-headed arrow is used to represent a biconditional statement.
P ⟷ Q
When you join two simple statements (also known as molecular statements) with the biconditional operator, we get:
P↔Q
P↔Q is read as “P if and only if Q.”
where P is known as the antecedent
where Q is known as the consequent
What is Ɐ?
It means “for all”
What is a floor log?
A floor-log or flog of a nonzero natural number n is:
flog(n) = highest power of 2 that divides n
E.g.
flog(4)=2
flog(3)=0
flog(24)=3
What is a theorem?
A theorem is a non-self-evident statement that has been proven to be true, either on the basis of generally accepted statements such as axioms or on the basis of previously established statements such as other theorems.
So it is a statement that is always true.
What is a turnstile?
Looks like ⊢
A ⊢ B
A proves B
What is a double turnstile?
Looks like ⊨
A ⊨ B
A models B
