Below are definitions and explanations of some of the basic concepts we use in Logic 1. You will need to learn these. Many of the concepts are inter-related. Where the definition of one term invokes another term that is defined here, I have created links between the definitions.
If there are any terms you think should be included, or if you spot any errors, then please email me.
You can scroll down to browse the glossary, or click one of the letters below to jump to definitions of terms starting with that letter. You can view a printable version of this page (without the menus) by clicking the "Print version" icon at the top right of this page.
|
Argument:
|
An argument comprises one or more statements as premises, and a statement as a conclusion. In English, words such as 'therefore', 'thus' and 'so' are often used to indicate that an argument is being given, with the following clause as the conclusion and the statements preceding it as the premises. Eg 'Edinburgh is in Scotland or England. Edinburgh is not in England. Therefore, Edinburgh is in Scotland'. Here, 'Edinburgh is in Scotland or England' and 'Edinburgh is not in England' are the premises and 'Edinburgh is in Scotland' is the conclusion.
|
|
Asymmetry:
|
A relation is asymmetrical if and only if, for every object x that can bear it to some object y, object y does not bear it to object x. Formally: ∀x∀y(Rxy → ¬Ryx)
Examples: 'is older than', 'is the mother of'.
|
|
Atomic formula:
|
An atomic formula is one that contains no connectives, eg 'P' (in propositional logic) or ' Pa' (in predicate logic). |
|
Basic truth tables:
|
The basic truth tables for each connective can be seen as defining that connective. They can be used to construct truth tables for more complex formulas containing more than one connective. You need to learn them. |
|
Connective:
|
A connective is a word or symbol that can be combined with one or more statements or formulas to give another (longer) properly formed statement or formula. Unary connectives, such as 'not', combine with just one formula. Binary connectives, such as 'and', combine with two formulas. A connective can be seen as being defined by its basic truth table. In Logic 1 we use five connectives: not (¬), and (∧), or (∨), if ... then ... (→) and if and only if (↔). |
|
Consistency:
|
A set of formulas is consistent if and only if it is possible that they are all true (at the same time).
AND
A set of formulas is consistent if and only if there is at least one interpretation in which they are all true. Invalidity can be defined in terms of consistency.
|
|
Contingency:
|
A formula is contingent if and only if it is possible that it is false AND it is possible that it is true.
AND
A formula is contingent if and only if there is at least one interpretation in which it is true and at least one interpretation in which it is false. The negation of a contingent formula is also contingent.
|
|
Contradiction:
|
A formula is a contracdiction if and only if it is impossible that it is true.
AND
A formula is a contracdiction if and only if there is no interpretation in which it is true. |
|
Counterexample:
|
When we give a counterexample to a statement, such as "It was sunny every day last week", we give a state of affairs that makes that statement false, eg "No, Tuesday was a miserable day". In logic, we make this notion of a counterexample more formal. The counterexample of a formula is an interpretation in which that formula is false. If there is a counterexample to a formula, then it is not a tautology. These notions are connected. When we claim that "It was sunny every day last week", we claim that "There was no day last week that was not sunny". The counterexample - the day that was not sunny - disproves that claim.
Similarly, when we claim that a sequent is valid, we claim that there is no interpretation in which premises and are true and the conclusion false, and the counterexample - which is an interpretation in which premises and are true and the conclusion false - disproves that claim. |
|
Counterexample set:
|
The counterexample set of a sequent is the set of formulas comprising the premises and the negation of the conclusion. |
|
Extension:
|
The extension of a one-place predicate is the set of all objects to which it applies. Eg, the extension of the predicate 'red' (or 'is red') is the set of all red things. The extension of a two place predicate (or relation). Is the set of ordered pairs of objects to which it applies. Eg, the extension of the predicate 'older than' (or 'is older than') for a restricted domain of John, George and David, where John is older than George, who is older than David, is {(John, George), (George, David), (John, David)}. Note that the person first in each pair is older than the second person, and that there are no further possible pairs that have that property. |
|
Formula:
|
A formula stands for one or more statements - it can be seen as a statement form. A formula in either propositional logic or predicate logic must be properly formed (this is akin to sentences being grammatical).
|
|
Identity:
|
Identity is a very important relation in logic. ' a is identical to b' means that a is the very same object as b. We use the 'equals' sign to indicate identity, eg ' a = b'. |
|
Inconsistency:
|
A set of formulas is inconsistent if and only if it is impossible that they are all true (at the same time).
AND
A set of or formulas is inconsistent if and only if there is no interpretation in which they are all true. If an inconsistent set that contains just one formula , that formula is a contradiction. Validity can be defined in terms of inconsistency.
|
|
Interpretation:
|
In propositional logic, an interpretation is an assignment of truth values to every atomic formula that occurs in the formula, set of formulas, sequent, etc. A full truth table has a row for every possible interpretation. In predicate logic, an interpretation gives:
(i) The domain of objects over which the variables in the formula(s) range;
(ii) The object referred to by each name in the formula(s);
(iii) The set of objects in the extension of each predicate used in the formula(s). |
|
Invalidity:
|
A sequent is invalid if and only if it is possible that the premises are true and the conclusion false.
AND
A sequent is invalid if and only if it there is at least one interpretation in which the premises are true and the conclusion false.
AND
A sequent is invalid if and only if the set of formulas comprising the premises and the negation of the conclusion (the counterexample set) is consistent. |
|
Irreflexivity:
|
A relation is irreflexive if and only if no object that can enter into that relation bears that relation to itself. Formally: ∀x¬Rxx
Examples: 'is older than', 'is the mother of'.
|
|
Literal:
|
In propositional logic, a literal is any closed atomic formula (ie one that contains no connectives) or its negation. Eg ¬P (in propositional logic) or Pa (in predicate logic). |
|
Logical equivalence:
|
Two formulas are logically equivalent if and only if it is impossible that one is true when the other is false.
AND
Two formulas are logically equivalent if and only if there is no interpretation in which one is true and the other is false.
AND
Two formulas A and B are logically equivalent if and only if (A ∧ ¬B) and (¬A ∧ B) are both inconsistent.
AND
Two formulas A and B are logically equivalent if and only if the biconditional (A ↔ B) is a tautology. |
|
Logical truth:
|
In predicate logic, a formula is a logical truth if and only if there is no interpretation in which it is false. |
|
Main connective or quantifier:
|
|
|
Name:
|
In predicate logic, we use lower case letters from the beginning of the alphabet (a, b, c, etc) to stand for names of objects.
|
|
Predicate:
|
Predicates are used to attribute properties (eg 'red', 'taller than') to objects.
In predicate logic, we use upper case letters from P onwards to stand for one-place predicates, and from R onwards to stand for two-or-more place predicates ( relations). Predicate letters are combined with names or variables to make formulas. Eg Pa says that object a has property P (or ' a is P'). |
|
Proof:
|
A proof of a sequent is a closed semantic tableau for the counterexample set of the sequent. (NB There is another method of proving sequents called derivation, though we do not cover this in the Logic 1 course). It can be shown that all provable sequents are valid, and that all valid sequents are provable. We indicate that a given sequent is provable by writing the double turnstile between the premises and the conclusion. |
|
Quantifier:
|
In predicate logic, we use two quantifiers: ∀ ('for all') and ∃ ('there exists (at least one)'). These can be combined with predicates and variables to make formulas. Eg ∀ xPx claims that every object (within the domain of discourse) is P. |
|
Reflexivity:
|
A relation is reflexive if and only if every object that can enter into that relation bears that relation to itself. Formally: ∀xRxx
Examples: 'is identical to', 'is the same colour as'.
|
|
Relation:
|
A relation is a two or more place predicate. English-language examples include 'is taller than', 'is later than', 'is 10 miles away from'. In predicate logic, we tend to use upper case lettes from R onwards to stand for relations. |
|
Scope:
|
The scope of a connective or quantifier is the sub-formula of which it is the main connective or quantifier, which will be the shortest properly-formed formula in which it occurs (NB this only works if the outermost parentheses are included in formulas of propositional logic, and if formulas with free variables are accepted in predicate logic). We say that connective A has wider scope than connective B if connective B occurs within the scope of connective A.
Examples:
The scope of '∧' in '(P → (Q ∧ (P ↔ Q)))' is '(Q ∧ (P ↔ Q))'
The scope of '∃' in '∀x[Px → (Qx ∧ ∃y(Px ↔ Qy))]' is '∃y(Px ↔ Qy)'
|
|
Semantic tableau:
|
|
|
Sequent:
|
A sequent is an argument form. It comprises a set of zero or more formulas that are the premises, and a formula that is the conclusion. A sequent can stand for any or all arguments that have the same form. We write a sequent by listing its premises separated by commas, followed by a colon, followed by the conclusion, eg 'P → Q, P : Q'.
To indicate, or claim, that the sequent is valid, we replace the colon with a turnstile. To indicate that it is provable, we replace the colon with a double turnstile. |
|
Statement:
|
A statement is a natural language (English, in our case) sentence that is capable of being true or false - one that states that the world is some particular way (eg 'Edinburgh is in Scotland'). Statements are therefore to be distinguished from questions or orders.
Some philosophers have argued that it is not statements themselves that are capable of being true or false, but propositions. This is covered in the Philosophy of Logic section at the end of the course, but need not concern us for the rest of the course.
Lets call statements that contain no connectives, such as 'Edinburgh is in Scotland', basic statements. When we formalize an English language sentence in propositional logic, we use a separate sentence letter ('P', 'Q', etc) to stand for each basic statement in the sentences we are formalizing, ie each basic statement becomes an atomic formula. |
|
Sub-formula:
|
A sub-formula is a properly formed formula that occurs as part of a longer formula. Any formula more complex than an individual literal (in propositional logic) or an individual predicate/name combination (in predicate logic) will have sub-formulas. Example: (P → (Q ∧ (P ↔ Q))) has the sub-formulas P, (Q ∧ (P ↔ Q)), Q, (P ↔ Q), P and Q.
We can use a parsing tree (see Logic notes section 3.7) to illustrate the sub-formulas of any given formula.
|
|
Symmetry:
|
A relation is symmetrical if and only if, for every object x that can bear it to some object y, object y also bears it to object x. Formally: ∀x∀y(Rxy → Ryx)
Examples: 'is married to', 'is 10 miles away from'.
|
|
Tableau rule:
|
The tableau rules for a connective or quantifier tell us how we must break down a formula of a particular format in a semantic tableau. You can determine the rule you need to use by:
(i) Determining the connective or quantifier in the formula that has the widest scope. If this is not a negation sign, then use the rule for the connective or quantifier.
(ii) If the connective or the quantifier with the widest scope is the negation sign, then you need to identify the connective or quantifier with the next widest scope. Then use the rule for the negation of that connective or quantifier.
You need to learn all the tableau rules. |
|
Tautology:
|
A formula is a tautology if and only if it is impossible that it is false.
AND
A formula is a tautology if and only if there no interpretation in which it is false (ie it is true in all interpretations). |
|
Transitivity:
|
A relation is transitive if and only if, where any object x bears it to any object y, and object y bears it to object z, then object x also bears it to object z. Formally: ∀x∀y∀z((Rxy ∧ Ryz) → Rxz)
Example: 'is older than' (if x is older than y and y is older than z, then x must be older than z).
|
|
Truth functionality:
|
A connective is truth functional if and only if the truth value of a statement or formula of which it is the main connective is determined by the truth values of the statements or formulas which it connects. |
|
Truth value:
|
In classical logic (the only logic we study in Logic 1), statements or formulas can have only one of two possible truth values: true and false. They cannot have neither truth value, and they cannot have both. Note that arguments and sequents cannot have truth values, they are the wrong kind of thing - only the statements or formulas that make up an argument or sequent can have truth values. |
|
Validity:
|
|
|
Variable:
|
In predicate logic, we use variables that range over the objects (or names of objects) in the domain of discourse. They are combined with quanitifiers and predicates to make formulas. |
