logic The logic of a system is the whole structure of rules that must be used for any reasoning within that system. Most of mathematics is based upon a well?understood structure of rules and is considered to be highly logical. lt is always necessary to state, or otherwise have it understood, what rules are being used before any logic can be applied.
statement A statement made within a logical system is a form of words (or symbols) which carries information. Within mathematics nearly everything is written in the form of statements.
Examples: The length of the radius is 4 cm. 3x + 2 = 7
argument An argument is a set of one or more statements which uses the logie of the system to show how one particular statement is arrived at.
true Within a system, a statement is said to be true when it is a known fact, or follows from some other true statement by means of a valid argument, or is considered to be self-evident.
false Within a system, a statement is said to be false when it is contrary to a statement known to be true.
undecidable Within a system, a statement is said to be undecidable when it cannot be shown to be either true or false.
assumption An assumption is a statement (true or false) which is to be taken as true for the purpose of the argument which follows.
premise -- assumption
self?evident A statement is described as self?evident when it is thought that no reasoning is necessary to demonstrate that the statement is true. This is often used to describe the most basie ideas of a system which are generally 'known'but are impossible to tIffine independently of the system.
Exampte: The statement 'Any two things which are each equal to a third thing must be equal to each other'could be seen as being self?evident.
intuitive Understanding (of a statement or a piece of knowledge) is described as intuitive when it is, or can be, reached without support of any argument.
axiom An axiom is a statement which
is assumed to be true, and is used as a basis for developing a system.
Any system of logic starts by saying clearly what axioms it uses.
proposition A proposition is a statement whose correctness (or otherwise) is to be shown by the use of an argument. It most often serves as an introduction by saying, in effect, what the argument is going to show.
valid A valid proof (or statement) is one in which all the arguments leading up to it are correct within the logie of the system being used.
invalid An invalid proof (or statement) is one which iS NOT valid.
counter-example A counter?example to a statement is a partieular instance of where that statement is not true. This makes the statement invalid. It only requires ONE counter?example to make a statement invalid. Example: 'All prime numbers are odd': a counter-example is 2
proof A proof is a sequence of statements (made up of axioms, assumptions and arguments) leading to the establishment of the truth of one finat statement.
direct proof A direct proof is a proof in which all the assumptions used are true and all the arguments are valid.
Example: To prove the proposition that adtling two odd numbers makes an even number. Any odd number is of thefi)rm 2n + 1
Adding two of this form protluces (2n + 1) + (2m + 1)= 2(n + m) + 2 = 2(n + m + 1), which is clearly even,
indirect proof An indirect proof is a proof in which one false assumption is made. Then, using valid arguments, a statement is arrived at which is clearly wrong, so the original assumption must have been wrong. This can only be used in a system in which statements must be either true orfalse, so that proving the first assumption is wrong allows only one possibility for its alternative form ? whichmust be the correct one.
Example: To prove ~2 is irrational. First assume that it is rational.
Then ~-2 = L' , where a, b are whole numbers with no common factors.
This leads to a' = 2b2, and a2 must be even and so must a.
Put a = 2c then ~2? = 2?'? and 2C2 = b 2 and b must be even.
But a,b had no common factors so both cannot be even. The assumption must be wrong and ?~?2 iS NOT rational. ~?2 must be irrational.
proof by contradiction indirect proof
reductio ad absurdum indirect proof
proof by exhaustion A proof by exhaustion is a proof which is established by working through EVERY possible case and finding no contradictions. Usually such a proof is only possible if the proposition to be proved has some restrictions placed upon it.
Example: The statement that 'Between every pair of square numbers there is at least one prime number'would be impossible to prove by looking at every possibility. However, by writing it as 'Between every pair of square numbers less than 1000 tizere'is at least one prime number'it can be proved by exhaustion - looking at every ease. This might then be considered as enough evidence to make it a conjecture about all numbers.
proof by induction A proof by induction is a proof which shows that IF one particular case is true then so is the next one; it also shows that one particular case is true. From those two aetions it mustfollow that ALL cases are true.
visual proof A visual proof is a proof in which the statements are presented in the form of diagrams.
Example: To prove the proposition that adtling two odd numbers makes an even number. Any odd number (?an be shown as
Adding two odd numbers is shown and clearly makes an even number.
'look?see'proof = visual proof
conjecture A conjecture is a statement which, although much evidence can be found to support it, has not been proved to be either true or false.
hypothesis A hypothesis is a statement which is usually thought to be true, and serves as a starting?point in looking for arguments (or evidence) to support it. This method is mostly used in statistics.
theorem A theorem is a statement which has been proved to be true.
lemnia A lemma is a theorem which is used in the proof of another theorem. Usually a lemma is of no importance in itself, but it is a useful way of simplifying the proof of thefinal theorem kv reducing its length.
corollary A corollary follows after a theorem and is a proposition which must
be true because of that theorem.
converse The converse of a theorem (or statement) is formed by taking the conclusion as the starting?point and having the starting?point as the conciusion. Though any theorem can be re-formed in this way, the result may or may not be true and it needs its own proof.
Example: One theorem states that if a triangle has two edges of equal length then the angles opposite to those edges are also equal in size. The converse is that if a triangle has two angles of equal size, then the edges opposite to those angles must be equal in length ? and that can also be proved.
contrapositive The contrapositive of a statement is fonned by taking the conclusion as the starting?point and the starting?point as the conclusion and then changing the sense of each (from positive to negative and vice versa). If the original statement was true, then the contrapositive must also be true.
Example: The statement If a number is even, it CAN be divided by twohas the contrapositive 'If a number CANNOT be divided by two, then it iS NOT even'.
necessary condition A necessary condition for a statement Q to be true is another statement P which MUST be true whenever statement Q is true, then statement P is said to be a necessary condition. When P is true then Q may be true orfalse, but when P isfalse, then 0 must also befalse.
Example: A necessary conditionfor the statement (Q)'x is divisible by 6'is statement (P)'x is even', but condition (P) by itself allows values such as 2, 4, 8 etc. which are clearly not divisible by 6
sufficient condition A sufficient condition for a statement Q to be true is another statement P which, when P is true, guarantees that statement Q MUST also be true. When statement P isfalse then statement Q may be true orfalse. Example: A sufficient condition for the statement (Q)'x is divisible by 6' is statement (P)x is divisible by 12', but condition (P) by itself excludes values such as 6, 18, 30, ete. which are also divisible by 6
necessary and suffieient condition A necessary and sufficient condition for a Statement to be true is a second Statement such that BOTH the first and the second Statement MUST be true at the same time. Both statements will be false together as well, but it cannot be that one is true and one isfalse.
Example: A necessary and sufficient condition J;gr the statement 'x is divisible by 6'is that 'x is even and divisible by 3'.
paradox A paradox is a valid statement which is self?contradictory or appears to be wrong. Paradoxes are important to the development of logic systems. Example: The barber shaves all the men in this village who do not shave themselves'seems a reasonably elear statement. However given that the barber is a man and lives in that village, who shaves the barber?
fallacy A fallacy is an argument which seems to be correct but which contains at least one error and, as a consequence, produces a final staternent which is clearly wrong. Though it is clear that the result is wrong, the error in the argument is usually (and ought to be) difficult to find.
Example: Let x = y: Then x 2 = xy and x2 ? y 2 = XY ?y 2
This gives (x + y)(x ? y) = y(x ? y) so that dividing both sides by (x ? y)
leaves x + y = y
From this result, putting x = y = 1 means 2 = 1
Or, subtracting yfrom both sides means x (= any number) = 0
The error is in dividing by (x ? y) which is zero.
symbols The conventional way of representing statements is by using capital letters. The letters most often used are P and Q.
Example: P could represent 'x is a prime number greater than 2'
P => Q where P and Q are staternents, is a symbolic way of saying T implies Q', OR 'when P is true then SO iS Q'; OR T is a sufficient condition for Q'. It also means that Q is a necessary conditionfor P.
Example: If P represents 'x is a prime number greater than 2', and Q represents 'x is an odd number', then P =* Q.
P <= Q where P and Q are staternents, is a symbolic way of saying T is implied by Q'; OR 'when Q is true, then so also iS P'; OR T is a necessary condition for Q'. It also means that Q is a sufficient conditionfor P.
Example: If P is 'x is divisible by 5', and Q is 'x is divisible by 10, then P e?? Q; which is a symbolic way of stating that a number which is divisible by 10 is also divisible by 5; or of saying that it is necessary (but not sufficient) that a number is divisible by 5 if it is to be divisible by 10.
P <=> Q where P and Q are staternents, is a symbolic way of saying that P and Q
must both be true (or false) together; OR T implies and is implied by Q';
OR T is a necessary and sufficient condition for Q'.
Example: If P is 'x is divisible by 6', and Q is 'x is divisible by 2 and 3',
then P => Q and P =* Q so P <~??> Q.
iff is a short way of writing 'if and only if' and is equivalent to Example: In the previous example thefinal statement could be T iff Q'.