Symbolic Logic

views updated

Symbolic Logic

Symbols

Statements

Conjunctions

Negation

Truth tables

Disjunctions

Algebra of statements

Implication

Resources

Logic is the study of the rules that underlie plausible reasoning in mathematics, science, law, and other disciplines. Symbolic logic, within the study of logic, is a system for expressing logical rules in an abstract, easily manipulated form with the use of symbols.

Symbols

in algebra, a letter such as x represents a number. Although the symbol gives no clue as to the value of the number, it can be used nevertheless in the formation of sums, products, etc. Similarly P, in geometry, stands for a point and can be used in describing segments, intersections, and the like.

In symbolic logic, a letter such as p stands for an entire statement. It may, for example, represent the statement, A triangle has three sides. In algebra, the plus sign joins two numbers to form a third number. In symbolic logic, a sign such as V connects two statements to form a third statement. For example, V replaces the word or and & replaces the word and. The following is a list of the symbols commonly encountered:

p, q, r, statements

υ or

^ and

~ it is not the case that=>

=> implies of If , then .

implies and is implied by or if and only if

Statements

statements Logic deals with statements, and statements vary extensively in the precision with which they may be made. If someone says, That is a good book, that is a statement. It is far less precise, however, than a statement such as Albany is the capital of New York State. A good book could be good because it is well printed and bound. It could be good because it is written in good style. It could tell a good story. It could be good in the opinion of one person but mediocre in the opinion of another.

The statements that logic handles with the greatest certainty are those that obey the law of the excluded middle, i.e., which are unambiguously true or false, not somewhere in between. It does not offer much help in areas such as literary criticism or history where statements simple enough to be unequivocally true or false tend also to be of little significance. As an antidote to illogical thinking, however, logic can be of value in any discipline.

By a statement in logic one means an assertion which is true or false. One may not know whether the statement is true or false, but it must be one or the other. For example, the Goldbach conjecture, Every even number greater than two is the sum of two primes, is either true or false, but no one knows which. It is a suitable statement for logical analysis.

Other words that are synonyms for statement are sentence, premise, and proposition.

Conjunctions

if p stands for the statement, All right angles are equal, and q the statement, Parallel lines never meet, one can make a single statement by joining them with and: All right angles are equal and parallel lines never meet. This can be symbolized p & q, using the inverted V-shaped symbol to stand for the conjunction and. Both the combined statement and the word and itself are called conjunctions. In ordinary English, there are several words in addition to and that can used for joining two statements conjunctively, for example, but. But is the preferred conjunction when one wants to alert the reader to a relationship that otherwise might seem contradictory. For example, He is 6 ft (1.8 m) tall, but he weighs 120 lb (54 kg). In logic the only conjunctive term is and.

Negation

negation is another logical operation. Unlike conjunction and disjunction, however, it is applied to a single statement. If one were to say, She is friendly, the negation of that statement would be, She is not friendly. The symbol for negation is tilde. It is placed in front of the statement to be negated, as in ~(p & q) or;~p. If p were the statement, She is friendly,;~p means She is not friendly, or more formally, It is not the case that she is friendly. Prefacing the statement with, It is not the case that, avoids embedding the negation in the middle of the statement to be negated. The symbol lips is read not p.

The statement ~p is true when p is false, and false when p is true. For example, if p is the statement <4,; ~p is the statement x4. Replacing x with S makes p false but; ~p true. If a boy, snubbed by the girl in She is friendly, were to hear the statement, he would say that it was false. He would say, She is not friendly, and mean it.

Truth tables

The fact that someone says something does not make it true.

Statements can be false as well as true. In logic, they must be one or the other, but not both and not neither. They must have a truth value, true or false, abbreviated T or F.

A very useful aid in symbolic logic is a truth table:
pq~ppΛqpVq
TTFTT
TFFFT
FTTFT
FFTFF

Whether a conjunction is true depends on the statements that make it up. If both of them are true, then the conjunction is true. If either one or both of them are false, the conjunction is false. For example, the familiar expression 3;<×;<; 7, which means ×;> 3 and;×;<; 7 is true only when both conditions are satisfied simultaneously, that is for numbers between 3 and 7.

Disjunctions

another word used in both ordinary English and in logic is or. Someone who says, Either he did not hear me, or he is being rude, is saying that at least one of those two possibilities is true. By connecting the two possibilities about which he or she is unsure, the speaker can make a statement of which he or she is sure.

In logic, or means and/or. If p and q are statements, p V q is the statement, called a disjunction, formed by connecting p and q with or, symbolized by V.

For example if p is the statement, Mary Doe may draw money from this account, and q is the statement, John Doe may draw money from this account, then p V q is the statement, Mary Doe may draw money from this account, or John Doe may draw money from this account.

The disjunction p V q is true when p, q, or both are true. In the example above, for instance, an account set up in the name of Mary or John Doe may be drawn on by both while they are alive and by the survivor if one of them should die. Had their account been set up in the name Mary and John Doe, both of them would have to sign the withdrawal slip, and the death of either one would freeze the account. Bankers, who tend to be careful about money, use and and or as one does in logic.

One use of truth tables is to test the equivalence of two symbolic expressions. Two expressions such as p and q are equivalent if whenever one is true the other is true, and whenever one is false the other is false. One can test the equivalence of;~(p V q) and;~p&;~q (as with the minus sign in algebra, ~ applies only to the statement which immediately follows it. If it is to apply to more than a single statement, parentheses must be used to indicate it):

pq~p~qpΛq~(pΛq)~pΛ~q
TTFFTFF
TFFTTFF
FTTFTFF
FFTTFTT

The expressions have the same truth values for all the possible values of p and q, and are therefore equivalent.

For instance, if p is the statement > 2 and q the statement <; 2, p V q is true when x is any number except 2. Then (p V q) is true only when x = 2. The negations p and q are x 2 and x 2 respectively. The only number for which;~p&;~q is true is also 2.

Algebra of statements

Equivalent propositions or statements can be symbolized with the two-headed arrow . In the preceding section it is shown the first of De Morgans rules:

1.;~(p V q);~p&;~q

2.;~(p & q);~pV;~q

Rules such as these are useful for simplifying and clarifying complicated expressions. Other useful rules are

3. p;~(~p)

4. p &(q V r); (p & q) V (p & r) (a distributive law for and applied to a disjunction)

5. p & q; q & p; p V q; qVp

6. (p & q) V r; p V (q V r); (p V q) V r; pV(qVr)

Each of these rules can be verified by writing out its truth table.

A truth table traces each of the various possibilities. To check rule 4 with its three different statements, p, q, and r, would require a truth table with eight lines. On occasion one may want to know the truth value of an expression such as ((T V F) & A (F V T)) V;\F where the truth values of particular statements have been entered in place of p1 q, etc. The steps in evaluating such an expression are as follows:

((T V F) Λ (F V T)) V F Given

(T A T) v T Truth tables for V,~

T V T Truth table for Λ

T Truth table for V

Such a compound expression might come from the run-on sentence, Roses are red or daisies are blue, and February has 30 days or March has 31 days; or it is not the case that May is in the fall. Admittedly, one is not likely to encounter such a sentence in ordinary conversation, but it illustrates how the rules of symbolic logic can be used to determine the ultimate truth of a complex statement. It also illustrates the process of replacing statements with known truth values instead of filling out a truth table for all the possible truth values. Since this example incorporates five different statements, a truth table of 32 lines would have been needed to run down every possibility.

Implication

in any discipline one seeks to establish facts and to draw conclusions based on observations and theories. One can do so deductively or inductively. In inductive reasoning, one starts with many observations and formulates an explanation that seems to fit. In deductive reasoning, one starts with premises and, using the rules of logical inference, draws conclusions from them. In disciplines such as mathematics, deductive reasoning is the predominant means of drawing conclusions. In fields such as psychology, inductive reasoning predominates, but once a theory has been formulated, it is both tested and applied through the processes of deductive thinking. It is in this that logic plays a role.

Basic to deductive thinking is the word implies, symbolized by =>. A statement p = > q means that whenever p is true, q is true also. For example, if p is the statement, x is in Illinois, and q is the statement x is in the United States, then p=> q is the statement, If x is in Illinois, then x is in the United States.

In logic as well as in ordinary English, there are many ways of translating p = > q into words: If p is true, then q is true; q is implied by p; p is true only if q is true; q is a necessary condition for p; p is a sufficient condition for q.

The implication p = > q has a truth table some find a little perplexing:

pqp =>q
TTT
TFF
FTT
FFT

The perplexing part occurs in the next to last line where a false value of p seems to imply a true value of q. The fact that p is false does not imply anything at all. The implication says only that q is true whenever p is. It does not say what happens when p is false. In the example given earlier, replacing x with Montreal makes both p and q false, but the implication itself is still true.

Implication has two properties that resemble the reflexive and transitive properties of equality. One, p = > p, is called a tautology. Tautologies, although widely used, do not add much to understanding. Why is the water salty? asks the little boy.

Because ocean water is salty, says his father.

The other property, If p = > q and q;=> r, then p = > r, is also widely used. In connecting two implications to form a third, it characterizes a lot of reasoning, formal and informal. If people take their vacation in January, there will be snow. If there is snow, people can go skiing. Let people take it in January. This property is called a syllogism.

A third property of equality, If a = b, then b = a, called symmetry, may or may not be shared by the implication p = > q. When it is, it is symbolized by the two-headed arrow used earlier, p; q. p; qmeans (p = > q) & (q;=> p). It can be read p and q are equivalent; p is true if and only if q is true; p implies and is implied by q; p is a necessary and sufficient condition for q; and p implies q, and conversely.

In p = > q, p is called the antecedent and q the consequent. If the antecedent and consequent are interchanged, the resulting implication, q;=> p, is called the converse. If one is talking about triangles, for example, there is a theorem, If two sides are equal, then the angles opposite the sides are equal. The converse is, If two angles are equal, then the sides opposite the angles are equal.

If an implication is true, it is never safe to assume that the converse is true as well. For example, If x lives in Illinois, then x lives in the United States, is a true implication, but its converse is obviously false. In fact, assuming that the converse of an implication is true is a significant source of fallacious reasoning. If the battery is dead, then the car will not start. True enough, but it is a good idea to check the battery itself instead of assuming the converse and buying a new one.

Implications are involved in three powerful lines of reasoning. One, known as the Rule of Detachment or by the Latin modus ponendo ponens, states simply If p = > q and p are both true, then q is true. This rule shows up in many areas. If x dies, then y is to receive $100,000. When x dies and proof is submitted to the insurance company, y gets a check for the

KEY TERMS

Logic The study of the rules that underlie deductive reasoning.

Statement A sentence that can be classified as either true or false, but not both.

money. The statements p = > q and p are called the premises and q the conclusion.

A second rule, known as modus tollendo tollens, says if p = > q is true and q is false, then p is false. If x ate the cake, then x was home. If x was not at home, then someone else ate the cake.

A third rule, modus tollerdo ponens, says that if p V q and p are true, then q is true. Mary or Ann broke the pitcher.

Ann did not; so Mary did. Of course, the validity of the argument depends upon establishing that both premises are true.

It may have been the cat.

Another type of argument is known as reductio ad absurdum, again from the Latin. Here, if one can show that;\~=> (q Λ;\~~q), then p must be true. That is, if assuming the negation of p leads to the absurdity of a statement which is both true and false at the same time, then p itself must be true.

Resources

BOOKS

Carroll, Lewis. Symbolic Logic. New York: Dover Publications Inc. 1958.

Christian, Robert R. Logic and Sets. Waltham, Massachusetts: Blaisdell Publishing Co., 1965.

Hedman, Shawn. A First Course in Logic: An Introduction in Model Theory, Proof Theory, Computability, and Complexity. Oxford, UK: Oxford University Press, 2004.

Solow, Daniel. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. New York: Wiley, 2002.

Sundstrom, Theodore A. Mathematical Reasoning: Writing and Proof. Upper Saddle River, NJ: Prentice Hall, 2003.

Suppes, Patrick, and Shirley Hill. First Course in Mathematical Logic. Waltham, Massachusetts : Blaisdell Publishing Co., 1964.

J. Paul Moulton