Logic II
2661
Glossary of symbols
Negation - ¬
The symbol ¬ is used to express negation in our language, the notion we commonly express in English using terms
like not, it is not the case that, non and un-.
Subset - ⊆
Given sets a subset a and b, we say that a is a subset of b, written a ⊆ b, provided every member of a is also a
member of b.
• Not subset ⊄
• Proper subset ⊂
• Proper superset ⊃
• Superset ⊇
• Not superset ⊅
Set – {}
Set of words are put into {}
Union - ∪
Elements that belong to set A or set B
Intersection - ∩
Elements that belong to both the sets, A and B
Empty set – Ø
Ø={}
Equality - =
Both sets have the same members
Element of - ∈
Set membership
• Not element of - ∉
Ordered pair - (a,b)
Collection of 2 elements
Cardinality - |B|, #B
The number of elements of set B
B = {7, 13, 15, 21}, |B|=4
Cartesian Product – A×B
Set of all ordered pairs from A and B
{3,5} × {7,8} = {(3,7), (3,8), (5,7), (5, 8) }
Universal Quantifier - ∀
The symbol ∀ is used to express universal claims, those we express in English using quantified phrases like
everything, each thing, all things, and anything. The combination ∀x is read “for every object x," or (somewhat
misleadingly) “for all x.”
,Existential Quantifier - ∃
The symbol 9 is used to express existential claims, those we express in English using such phrases as something, at
least one thing, a, and an.
Biconditional - ↔
Our final connective is called the material biconditional symbol. Given any sentences P and Q there is another
sentence formed by connecting these by means of the biconditional: P $ Q. A sentence of the form P $ Q is true if
and only if P and Q have the same truth value, that is, either they are both true or both false.
Implication - →
The symbol → is used to combine two sentences P and Q to form a new sentence P → Q, called a material
conditional.
Contradiction - ⊥
In order to apply the method of proof by contradiction, it is important that you understand what a contradiction is,
since that is what you need to prove from your temporary assumption. Intuitively, a contradiction is any claim that
cannot possibly be true, or any set of claims which cannot all be true simultaneously.
TRUTH TABLE
P Q P∩Q P∪Q P→Q P↔Q ¬P ¬Q
T T T T T T F F
T F F T F F F T
F T F T T F T F
F F F F T T T T
Atomic sentences
Atomic sentences correspond to the most simple sentences of English, atomic sentences consisting of some names
connected by a predicate. Examples are Max ran, Max saw Claire, and Claire gave Scruffy to Max. Similarly, in fol
atomic sentences are formed by combining names (or individual constants, as they are often called) and
predicates, though the way they are combined is a bit different from English, as you will see.
This language has names like b, e, and n2, and predicates like Cube, Larger, and Between.
Individual constants
Individual constants are simply symbols that are used to refer to some fixed individual object. They are the fol
analogue of names, though in fol we generally don't capitalize them. For example, we might use max as an
individual constant to denote a particular person, named Max, or 1 as an individual constant to denote a particular
number, the number one.
Predicate symbols
Predicate symbols are symbols used to express some property of objects or predicate or relation some relation
between objects. Because of this, they are also sometimes called symbols relation symbols. As in English,
predicates are expressions that, when combined with names, form atomic sentences. But they don't correspond
exactly to the predicates of English grammar.
Arity
The term “arity" comes from the fact that predicates taking one argument are called unary, those taking two are
binary, those taking three are ternary, and so forth.
In Tarski's World we restrict ourselves to predicates with arities 1, 2, and 3.
Arity 1: Cube, Tet, Dodec, Small, Medium, Large
Arity 2: Smaller, Larger, LeftOf, RightOf, BackOf, FrontOf, SameSize, Same -Shape, SameRow, SameCol, Adjoins, =
Arity 3: Between
,Table 1.1: Blocks language predicates
.
Determinate property
Fol, however, assumes that every predicate is interpreted by a determinate property or relation. By a determinate
property, we mean a property for which, given any object, there is a definite fact of the matter whether or not the
object has the property.
Infix vs. prefix notation
In the case of the identity symbol, we put the two required names on either side of the predicate, as in a = b. This
is called “infix" notation, since the predicate symbol = appears in between its two arguments. With the other
predicates we use “prefix" notation: the predicate precedes the arguments.
In a language with function symbols
• Complex terms are typically formed by putting a function symbol of arity n in front of n terms (simple or
complex).
• Complex terms are used just like names (simple terms) in forming atomic sentenc es.
• In fol, complex terms are assumed to refer to one and only one object.
Definition The terms of first-order arithmetic are formed in the following way:
1. The names 0; 1 are terms.
2. If t1 ; t2 are terms, then the expressions (t1 + t2 ) and (t1 x t2 ) are also terms.
3. Nothing is a term unless it can be obtained by repeated application of (1) and (2).
, The Logic of Atomic Sentences
Valid and sound arguments
Just what do we mean by logical consequence? Or rather, since this phrase is sometimes used in quite different
contexts, what does a logician mean by logical consequence?
A few examples will help. First, let's say that an argument is any series of statements in which one (called the
conclusion) is meant to follow from, or be supported by, the others (called the premises).
There are many devices in ordinary language for indicating premises and conclusions of arguments. Words like
hence, thus, so, and consequently are used to indicate that what follows is the conclusion of an argument. The
words because, since, after all, and the like are generally used to indicate premises.
Here are a couple of examples of arguments:
All men are mortal. Socrates is a man. So, Socrates is mortal.
Lucretius is a man. After all, Lucretius is mortal and all men are mortal.
One difference between these two arguments is the placement of the conclusion.
In the first argument, the conclusion comes at the end, while in the second, it comes at the start. This is indicated
by the words so and after all, respectively. A more important difference is that the first argument is good, while
the second is bad. We will say that the first argument is logically valid, or that its conclusion is a logical
consequence of its premises. The reason we say this is that it is impossible for this co nclusion to be false if the
premises are true. In contrast, our second conclusion might be false (suppose Lucretius is my pet goldfish), even
though the premises are true (goldfish are notoriously mortal). The second conclusion is not a logical consequence
of its premises.
Roughly speaking, an argument is logically valid if and only if the conclusion must be true on the assumption that
the premises are true. Notice that this does not mean that an argument's premises have to be true in order for it
to be valid. When we give arguments, we naturally intend the premises to be true, but sometimes we're wrong
about that.
Sound Arguments
A valid argument is one that guarantees the truth of its conclusion on the assumption that the premises are true.
Now, as we said before, when we actually present arguments, we want them to be more than just valid: we also
want the premises to be true. If an argument is valid and the premises are also true, then the argument is said to
be sound. Thus a sound argument insures the truth of its conclusion. The argument about Socrates given above
was not only valid, it was sound, since its premises were true. (He was not, contrary to rumors, a robot.) But here
is an example of a valid argument that is not sound:
All rich actors are good actors. Brad Pitt is a rich actor. So he must be a good actor.
The reason this argument is unsound is that its first premise is false. Because of this, although the argument is
indeed valid, we are not assured that the conclusion is true. It may be, but then again it may not. We in fact think
that Brad Pitt is a good actor, but the present argument does not show this.
Logic focuses, for the most part, on the validity of arguments, rather than their soundness. There is a simple reason
for this. The truth of an argument's premises is generally an issue that is none of the logician's business: the truth
of “Socrates is a man" is something historians had to ascertain; the falsity of “All rich actors are good actors" is
something a movie critic might weigh in about. What logicians can tell you is how to reason correctly, given what
you know or believe to be true. Making sure that the premises of your arguments are true is something that, by
and large, we leave up to you.
Fitch format
