Friday, January 9, 2009

LOGIC AND SETS


1.1. Sentences

In this section, we look at sentences, their truth or falsity, and ways of combining or connecting sentences

to produce new sentences.

A sentence (or proposition) is an expression which is either true or false. The sentence \2 + 2 = 4" is

true, while the sentence \_ is rational" is false. It is, however, not the task of logic to decide whether

any particular sentence is true or false. In fact, there are many sentences whose truth or falsity nobody

has yet managed to establish; for example, the famous Goldbach conjecture that \every even number

greater than 2 is a sum of two primes".

There is a defect in our de_nition. It is sometimes very di_cult, under our de_nition, to determine

whether or not a given expression is a sentence. Consider, for example, the expression \I am telling a

lie"; am I?

Since there are expressions which are sentences under our de_nition, we proceed to discuss ways of

connecting sentences to form new sentences.

Let p and q denote sentences.

Definition. (CONJUNCTION) We say that the sentence p ^ q (p and q) is true if the two sentences p,

q are both true, and is false otherwise.

Example 1.1.1. The sentence \2 + 2 = 4 and 2 + 3 = 5" is true.

Example 1.1.2. The sentence \2 + 2 = 4 and _ is rational" is false.

1 of 9

Definition. (DISJUNCTION) We say that the sentence p _ q (p or q) is true if at least one of two

sentences p, q is true, and is false otherwise.

Example 1.1.3. The sentence \2 + 2 = 2 or 1 + 3 = 5" is false.

Example 1.1.4. The sentence \2 + 2 = 4 or _ is rational" is true.

Remark. To prove that a sentence p_q is true, we may assume that the sentence p is false and use this

to deduce that the sentence q is true in this case. For if the sentence p is true, our argument is already

complete, never mind the truth or falsity of the sentence q.

Definition. (NEGATION) We say that the sentence p (not p) is true if the sentence p is false, and is

false if the sentence p is true.

Example 1.1.5. The negation of the sentence \2 + 2 = 4" is the sentence \2 + 2 6= 4".

Example 1.1.6. The negation of the sentence \_ is rational" is the sentence \_ is irrational".

Definition. (CONDITIONAL) We say that the sentence p ! q (if p, then q) is true if the sentence p

is false or if the sentence q is true or both, and is false otherwise.

Remark. It is convenient to realize that the sentence p ! q is false precisely when the sentence p is

true and the sentence q is false. To understand this, note that if we draw a false conclusion from a true

assumption, then our argument must be faulty. On the other hand, if our assumption is false or if our

conclusion is true, then our argument may still be acceptable.

Example 1.1.7. The sentence \if 2 + 2 = 2, then 1 + 3 = 5" is true, because the sentence \2 + 2 = 2"

is false.

Example 1.1.8. The sentence \if 2 + 2 = 4, then _ is rational" is false.

Example 1.1.9. The sentence \if _ is rational, then 2 + 2 = 4" is true.

Definition. (DOUBLE CONDITIONAL) We say that the sentence p $ q (p if and only if q) is true if

the two sentences p, q are both true or both false, and is false otherwise.

Example 1.1.10. The sentence \2 + 2 = 4 if and only if _ is irrational" is true.

Example 1.1.11. The sentence \2 + 2 6= 4 if and only if _ is rational" is also true.

If we use the letter T to denote \true" and the letter F to denote \false", then the above _ve de_nitions

can be summarized in the following \truth table":

p q p ^ q p _ q p p ! q p $ q

T T T T F T T

T F F T F F F

F T F T T T F

F F F F T T T

Remark. Note that in logic, \or" can mean \both". If you ask a logician whether he likes tea or co_ee,

do not be surprised if he wants both!

2 of 9

Example 1.1.12. The sentence (p _ q) ^ (p ^ q) is true if exactly one of the two sentences p, q is true,

and is false otherwise; we have the following \truth table":

p q p ^ q p _ q p ^ q (p _ q) ^ (p ^ q)

T T T T F F

T F F T T T

F T F T T T

F F F F T F

1.2. Tautologies and Logical Equivalence

Definition. A tautology is a sentence which is true on logical ground only.

Example 1.2.1. The sentences (p ^ (q ^ r)) $ ((p ^ q) ^ r) and (p ^ q) $ (q ^ p) are both tautologies.

This enables us to generalize the de_nition of conjunction to more than two sentences, and write, for

example, p ^ q ^ r without causing any ambiguity.

Example 1.2.2. The sentences (p _ (q _ r)) $ ((p _ q) _ r) and (p _ q) $ (q _ p) are both tautologies.

This enables us to generalize the de_nition of disjunction to more than two sentences, and write, for

example, p _ q _ r without causing any ambiguity.

Example 1.2.3. The sentence p _ p is a tautology.

Example 1.2.4. The sentence (p ! q) $ (q ! p) is a tautology.

Example 1.2.5. The sentence (p ! q) $ (p _ q) is a tautology.

Example 1.2.6. The sentence (p $ q) $ ((p _ q) ^ (p ^ q)) is a tautology; we have the following \truth

table":

p q p $ q (p $ q) (p _ q) ^ (p ^ q) (p $ q) $ ((p _ q) ^ (p ^ q))

T T T F F T

T F F T T T

F T F T T T

F F T F F T

The following are tautologies which are commonly used. Let p, q and r denote sentences.

DISTRIBUTIVE LAW. The following sentences are tautologies:

(a) (p ^ (q _ r)) $ ((p ^ q) _ (p ^ r));

(b) (p _ (q ^ r)) $ ((p _ q) ^ (p _ r)).

DE MORGAN LAW. The following sentences are tautologies:

(a) (p ^ q) $ (p _ q);

(b) (p _ q) $ (p ^ q).

INFERENCE LAW. The following sentences are tautologies:

(a) (MODUS PONENS) (p ^ (p ! q)) ! q;

(b) (MODUS TOLLENS) ((p ! q) ^ q) ! p;

(c) (LAW OF SYLLOGISM) ((p ! q) ^ (q ! r)) ! (p ! r).

3 of 9

These tautologies can all be demonstrated by truth tables. However, let us try to prove the _rst

Distributive law here.

Suppose _rst of all that the sentence p ^ (q _ r) is true. Then the two sentences p, q _ r are both

true. Since the sentence q _ r is true, at least one of the two sentences q, r is true. Without loss of

generality, assume that the sentence q is true. Then the sentence p^q is true. It follows that the sentence

(p ^ q) _ (p ^ r) is true.

Suppose now that the sentence (p ^ q) _ (p ^ r) is true. Then at least one of the two sentences (p ^ q),

(p^r) is true. Without loss of generality, assume that the sentence p^q is true. Then the two sentences

p, q are both true. It follows that the sentence q _ r is true, and so the sentence p ^ (q _ r) is true.

It now follows that the two sentences p^(q _r) and (p^q)_(p^r) are either both true or both false,

as the truth of one implies the truth of the other. It follows that the double conditional (p ^ (q _ r)) $ ((p ^ q) _ (p ^ r)) is a tautology.

Definition. We say that two sentences p and q are logically equivalent if the sentence p $ q is a

tautology.

Example 1.2.7. The sentences p ! q and q ! p are logically equivalent. The latter is known as the

contrapositive of the former.

Remark. The sentences p ! q and q ! p are not logically equivalent. The latter is known as the

converse of the former.

1.3. Sentential Functions and Sets

In many instances, we have sentences, such as \x is even", which contains one or more variables. We

shall call them sentential functions (or propositional functions).

Let us concentrate on our example \x is even". This sentence is true for certain values of x, and is

false for others. Various questions arise:

_ What values of x do we permit?

_ Is the statement true for all such values of x in question?

_ Is the statement true for some such values of x in question?

To answer the _rst of these questions, we need the notion of a universe. We therefore need to consider

sets.

We shall treat the word \set" as a word whose meaning everybody knows. Sometimes we use the

synonyms \class" or \collection". However, note that in some books, these words may have di_erent

meanings!

The important thing about a set is what it contains. In other words, what are its members? Does it

have any? If P is a set and x is an element of P, we write x 2 P.

A set is usually described in one of the two following ways:

_ By enumeration, e.g. f1; 2; 3g denotes the set consisting of the numbers 1; 2; 3 and nothing else;

_ By a de_ning property (sentential function) p(x). Here it is important to de_ne a universe U to

which all the x have to belong. We then write P = fx : x 2 U and p(x) is trueg or, simply,

P = fx : p(x)g.

The set with no elements is called the empty set and denoted by ;.

4 of 9

Example 1.3.1. N = f1; 2; 3; 4; 5; :::g is called the set of natural numbers.

Example 1.3.2. Z = f: : : ;��2;��1; 0; 1; 2; : : :g is called the set of integers.

Example 1.3.3. fx : x 2 N and �� 2 <>2g = f1g.

Example 1.3.4. fx : x 2 Z and �� 2 <>2g = f��1; 0; 1g.

Example 1.3.5. fx : x 2 N and �� 1 <>1g = ;.

1.4. Set Functions

Suppose that the sentential functions p(x), q(x) are related to sets P, Q with respect to a given universe,

i.e. P = fx : p(x)g and Q = fx : q(x)g. We de_ne

_ the intersection P \ Q = fx : p(x) ^ q(x)g;

_ the union P [ Q = fx : p(x) _ q(x)g;

_ the complement P = fx : p(x)g; and

_ the di_erence P n Q = fx : p(x) ^ q(x)g.

The above are also sets. It is not di_cult to see that

_ P \ Q = fx : x 2 P and x 2 Qg;

_ P [ Q = fx : x 2 P or x 2 Qg;

_ P = fx : x 62 Pg; and

_ P n Q = fx : x 2 P and x 62 Qg.

We say that the set P is a subset of the set Q, denoted by P _ Q or by Q _ P, if every element of P

is an element of Q. In other words, if we have P = fx : p(x)g and Q = fx : q(x)g with respect to some

universe U, then we have P _ Q if and only if the sentence p(x) ! q(x) is true for all x 2 U.

We say that two sets P and Q are equal, denoted by P = Q, if they contain the same elements, i.e.

if each is a subset of the other, i.e. if P _ Q and Q _ P.

Furthermore, we say that P is a proper subset of Q, denoted by P _ Q or by Q _ P, if P _ Q and

P 6= Q.

The following results on set functions can be deduced from their analogues in logic.

DISTRIBUTIVE LAW. If P; Q;R are sets, then

(a) P \ (Q [ R) = (P \ Q) [ (P \ R);

(b) P [ (Q \ R) = (P [ Q) \ (P [ R).

DE MORGAN LAW. If P;Q are sets, then with respect to a universe U,

(a) (P \ Q) = P [ Q;

(b) (P [ Q) = P \ Q.

We now try to deduce the _rst Distributive law for set functions from the _rst Distributive law for

sentential functions.

Suppose that the sentential functions p(x), q(x), r(x) are related to sets P, Q, R with respect to a

given universe, i.e. P = fx : p(x)g, Q = fx : q(x)g and R = fx : r(x)g. Then

P \ (Q [ R) = fx : p(x) ^ (q(x) _ r(x))g

and

(P \ Q) [ (P \ R) = fx : (p(x) ^ q(x)) _ (p(x) ^ r(x))g:

5 of 9

Suppose that x 2 P \ (Q [ R). Then p(x) ^ (q(x) _ r(x)) is true. By the _rst Distributive law for

sentential functions, we have that

(p(x) ^ (q(x) _ r(x))) $ ((p(x) ^ q(x)) _ (p(x) ^ r(x)))

is a tautology. It follows that (p(x) ^ q(x)) _ (p(x) ^ r(x)) is true, so that x 2 (P \ Q) [ (P \ R). This

gives

P \ (Q [ R) _ (P \ Q) [ (P \ R): (1)

Suppose now that x 2 (P \ Q) [ (P \ R). Then (p(x) ^ q(x)) _ (p(x) ^ r(x)) is true. It follows from the

_rst Distributive law for sentential functions that p(x) ^ (q(x) _ r(x)) is true, so that x 2 P \ (Q [ R).

This gives

(P \ Q) [ (P \ R) _ P \ (Q [ R): (2)

The result now follows on combining (1) and (2).

1.5. Quanti_er Logic

Let us return to the example \x is even" at the beginning of Section 1.3.

Suppose now that we restrict x to lie in the set Z of all integers. Then the sentence \x is even" is only

true for some x in Z. It follows that the sentence \some x 2 Z are even" is true, while the sentence \all

x 2 Z are even" is false.

In general, consider a sentential function of the form p(x), where the variable x lies in some clearly

stated set. We can then consider the following two sentences:

_ 8x, p(x) (for all x, p(x) is true); and

_ 9x, p(x) (for some x, p(x) is true).

Definition. The symbols 8 (for all) and 9 (for some) are called the universal quanti_er and the exis-

tential quanti_er respectively.

Note that the variable x is a \dummy variable". There is no di_erence between writing 8x, p(x) or

writing 8y, p(y).

Example 1.5.1. (LAGRANGE'S THEOREM) Every natural number is the sum of the squares of four

integers. This can be written, in logical notation, as

8n 2 N; 9a; b; c; d 2 Z; n = a2 + b2 + c2 + d2:

Example 1.5.2. (GOLDBACH CONJECTURE) Every even natural number greater than 2 is the sum

of two primes. This can be written, in logical notation, as

8n 2 N n f1g; 9p; q prime; 2n = p + q:

It is not yet known whether this is true or not. This is one of the greatest unsolved problems in

mathematics.

1.6. Negation

Our main concern is to develop a rule for negating sentences with quanti_ers. Let me start by saying

that you are all fools. Naturally, you will disagree, and some of you will complain. So it is natural to

suspect that the negation of the sentence 8x, p(x) is the sentence 9x, p(x).

6 of 9

There is another way to look at this. Let U be the universe for all the x. Let P = fx : p(x)g. Suppose

_rst of all that the sentence 8x, p(x) is true. Then P = U, so P = ;. But P = fx : p(x)g, so that if

the sentence 9x, p(x) were true, then P 6= ;, a contradiction. On the other hand, suppose now that the

sentence 8x, p(x) is false. Then P 6= U, so that P 6= ;. It follows that the sentence 9x, p(x) is true.

Now let me moderate a bit and say that some of you are fools. You will still complain, so perhaps

none of you are fools. It is then natural to suspect that the negation of the sentence 9x, p(x) is the

sentence 8x, p(x).

To summarize, we simply \change the quanti_er to the other type and negate the sentential function".

Suppose now that we have something more complicated. Let us apply bit by bit our simple rule. For

example, the negation of

8x; 9y; 8z; 8w; p(x; y; z;w)

is

9x; (9y; 8z; 8w; p(x; y; z;w));

which is

9x; 8y; (8z; 8w; p(x; y; z;w));

which is

9x; 8y; 9z; (8w; p(x; y; z;w));

which is

9x; 8y; 9z; 9w; p(x; y; z;w):

It is clear that the rule is the following: Keep the variables in their original order. Then, alter all the

quanti_ers. Finally, negate the sentential function.

Example 1.6.1. The negation of the Goldbach conjecture is, in logical notation,

9n 2 N n f1g; 8p; q prime; 2n 6= p + q:

In other words, there is an even natural number greater than 2 which is not the sum of two primes. In

summary, to disprove the Goldbach conjecture, we simply need one counterexample!

7 of 9

Problems for Chapter 1

1. Using truth tables or otherwise, check that each of the following is a tautology:

a) p ! (p _ q) b) ((p ^ q) ! q) ! (p ! q)

c) p ! (q ! p) d) (p _ (p ^ q)) $ p

e) (p ! q) $ (q ! p)

2. Decide (and justify) whether each of the following is a tautology:

a) (p _ q) ! (q ! (p ^ q)) b) (p ! (q ! r)) ! ((p ! q) ! (p ! r))

c) ((p _ q) ^ r) $ (p _ (q ^ r)) d) (p ^ q ^ r) ! (s _ t)

e) (p ^ q) ! (p ! q) f) p ! q $ (p ! q)

g) (p ^ q ^ r) $ (p ! q _ (p ^ r)) h) ((r _ s) ! (p ^ q)) ! (p ! (q ! (r _ s)))

i) p ! (q ^ (r _ s)) j) (p ! q ^ (r $ s)) ! (t ! u)

k) (p ^ q) _ r $ ((p _ q) ^ r) l) (p q) (q p).

m) (p ^ (q _ (r ^ s))) $ ((p ^ q) _ (p ^ r ^ s))

3. For each of the following, decide whether the statement is true or false, and justify your assertion:

a) If p is true and q is false, then p ^ q is true.

b) If p is true, q is false and r is false, then p _ (q ^ r) is true.

c) The sentence (p $ q) $ (q $ p) is a tautology.

d) The sentences p ^ (q _ r) and (p _ q) ^ (p _ r) are logically equivalent.

4. List the elements of each of the following sets:

a) fx 2 N : x2 < 45g b) fx 2 Z : x2 < 45g c) fx 2 R : x2 + 2x = 0g d) fx 2 Q : x2 + 4 = 6g e) fx 2 Z : x4 = 1g f) fx 2 N : x4 = 1g

5. How many elements are there in each of the following sets? Are the sets all di_erent?

a) ; b) f;g c) ff;gg d) f;; f;gg e) f;; ;g

6. Let U = fa; b; c; dg, P = fa; bg and Q = fa; c; dg. Write down the elements of the following sets:

a) P [ Q b) P \ Q c) P d) Q

7. Let U = R, A = fx 2 R : x > 0g, B = fx 2 R : x > 1g and C = fx 2 R : x < 2g. Find each of the

following sets:

a) A [ B b) A [ C c) B [ C d) A \ B

e) A \ C f) B \ C g) A h) B

i) C j) A n B k) B n C

8. List all the subsets of the set f1; 2; 3g. How many subsets are there?

9. A, B, C, D are sets such that A [ B = C [ D, and both A \ B and C \ D are empty.

a) Show by examples that A \ C and B \ D can be empty.

b) Show that if C _ A, then B _ D.

10. Suppose that P, Q and R are subsets of N. For each of the following, state whether or not the

statement is true, and justify your assertion by studying the analogous sentences in logic:

a) P [ (Q \ R) = (P [ Q) \ (P [ R). b) P _ Q if and only if Q _ P.

c) If P _ Q and Q _ R, then P _ R.

8 of 9

11. For each of the following sentences, write down the sentence in logical notation, negate the sentence,

and say whether the sentence or its negation is true:

a) Given any integer, there is a larger integer.

b) There is an integer greater than all other integers.

c) Every even number is a sum of two odd numbers.

d) Every odd number is a sum of two even numbers.

e) The distance between any two complex numbers is positive.

f) All natural numbers divisible by 2 and by 3 are divisible by 6.

[Notation: Write x j y if x divides y.]

g) Every integer is a sum of the squares of two integers.

h) There is no greatest natural number.

12. For each of the following sentences, express the sentence in words, negate the sentence, and say

whether the sentence or its negation is true:

a) 8z 2 N, z2 2 N b) 8x 2 Z, 8y 2 Z, 9z 2 Z, z2 = x2 + y2

c) 8x 2 Z, 8y 2 Z, (x > y) ! (x 6= y) d) 8x; y; z 2 R, 9w 2 R, x2 + y2 + z2 = 8w

13. Let p(x; y) be a sentential function with variables x and y. Discuss whether each of the following is

true on logical grounds only:

a) (9x; 8y; p(x; y)) ! (8y; 9x; p(x; y)) b) (8y; 9x; p(x; y)) ! (9x; 8y; p(x; y))

9 of 9

39 comments:

Saepul Misbahudin said...

thank for your attention, so i've to learn more to you

Siebel Expert said...

u r welcome visit. TechnicalContents.com

衣服 said...

小遊戲,同志聊天室,色情小遊戲,貼圖區,哈比寬頻成人,嘟嘟成人,玩美女人,視訊交友,自拍貼圖,正妹計時器,無碼影片,情人視訊,正妹牆,聊天室,ut聊天室,視訊聊天室,情色,微風成人,豆豆聊天室,視訊美女,85cc成人片,85cc成人片觀看,交友戀愛進行室,嘟嘟成人網,成人,色情,美女,色情小說,情色貼圖,情色小說,交友覓戀會館,情色文學,交友104速配網,視訊交友,成人韭南籽,18成人,ut男同志聊天室,成人圖片區,交友104相親網,0951成人頻道下載,男同志聊天室,

六福村 said...

經驗是良師,可惜學費貴 ..................................................

請客 said...

nice to know you ~........................................

touch said...

我新來的~大家可交個朋友嗎(・ˍ・)........................................

香蕉哥哥 said...

IT IS A VERY NICE SUGGESTION, THANK YOU LOTS! ........................................

治男治男 said...

It's great!!..................................................

邦雄 said...

愛看您的新文章!加油! ........................................

昱廷昱廷 said...

說「吃虧就是便宜的人」,多半不是吃虧的人。..................................................

怡逸凡君 said...

廢話不多,祝你順心~^^........................................

祥傑 said...

愛,拆開來是心和受兩個字。用心去接受對方的一切,用心去愛對方的所有。...............................................................

懿綺 said...

很棒的分享~如有打擾之處,敬請原諒!.............................................

皇豪 said...

成人卡通 視訊34c 母子亂倫聊天室 免費無碼片 台灣交友網 日本女優無碼 無名小站性感美女影片 影片試看 偷拍,影片 基隆聊天室 女性愛愛 性愛自拍 18成人網站 少女色情 洪爺成人影城 彩虹a片 情色卡通線上看 麗的色情小遊 一夜情a片 aio愛情館影片免費383 完美女人 玩美影城 性感美女 辣妹鋼管脫衣秀 人妻短片下載 熟女貼圖 a片下載 視訊聊天室 a圖看到爽 限制級寫真集 85cc免費看成人片 微風成人a片本土 嘟嘟 色情777 熊貓貼圖 援交自拍影片 情人趣味用品 免費脫衣 免費av片觀賞 洪爺影城 大奶阿尼 mofosex. 下載a圖 日本av巨乳 性愛光碟 後宮電影院18jack 限制級 live0204 免費看性愛影片 正妹走光露點

730A_ngelinaRabideau0 said...

人有兩眼一舌,是為了觀察倍於說話的緣故。..................................................

昱宏彥良 said...

一個人想法的大小,決定他成就的大小。 ....................................................

judyrod said...

Where theres a will theres a way. ............................................................

esthermelvin said...

文章不求沽名釣譽,率性就是真的..................................................................

玫友 said...

恨一個人,比原諒一個人,更傷力氣。..................................................................

正玲正玲 said...

這麼好的部落格,以後看不到怎麼辦啊!!......................................................................

婷珊 said...

在莫非定律中有項笨蛋定律:「一個組織中的笨蛋,恆大於等於三分之二。」.................................................................                           

江婷 said...

人不能像動物一樣活著,而應該追求知識和美德.................................................................

啟均 said...

當一個人內心能容納兩樣相互衝突的東西,這個人便開始變得有價值了。............................................................

江冠彭珮李佳宏陽筠 said...

安安!剛開始玩這個,來這裡逛一下^^............................................................

云依恩HFH謝鄭JTR安 said...

不只BLOG內容很棒留言也很精采 XDDDD..................................................................

姿柯瑩柯dgdd憶曾g智曾 said...

If you lend someone $20 and never see that person again, it was probably worth it.............................................................

天花天花 said...

We could learn a lot from crayons. Some are sharp, some are pretty and some are dull, Some have weird names , and all are different colors, but they all have to live in the same box .............................................................

茂慧茂慧 said...

如果你批評他人。你就沒有時間付出愛............................................................

琬安琬安 said...

河水永遠是相同的,可是每一剎那又都是新的。. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

江彥璋江彥璋江彥璋 said...

凡事三思而行,跑得太快是會滑倒的。..................................................

佩吳璇佩吳璇 said...

Man proposes, God disposes..................................................................

淑林林松 said...

人生中最好的禮物就是屬於自己的一部份..................................................

惠慧萍婷 said...

Pen and ink is wits plough...................................................................

玄王季玄王季玄王季 said...

多謝大大的分享......good............................................................

宋張建宇瑞正 said...

一個人的價值,應該看他貢獻了什麼,而不是他取得了什麼............................................................

8468 said...

Never put off till tomorrow what may be done today..................................................................

怡屏 said...

成功可招引朋友,挫敗可考驗朋友......................................................................

淑徐承翰承翰娟 said...

來看你了~心在、愛在、牽掛在,幸福才會繁衍不息^^...............................................................

惠NorrisBradwell041花 said...

好的blog需要我們一起努力!........................................