- 42

- 2

**1. Homework Statement**

Problem from a discrete structures online open course. I don't have the answers and was quite confused about this unit, so I was hoping to check my work/ clarify a few questions.

Problem 5.5. Express each of the following predicates and propositions in formal logic notation. The domain of discourse is the nonnegative integers, N. Moreover, in addition to the propositional operators, variables and quantifiers, you may define predicates using addition, multiplication, and equality symbols, but no constants (like 0, 1,. . .) and no exponentiation (like [itex]x^y[/itex]). For example, the proposition “n is an even number” could be written (

##\exists{m}. (m+m=n)##

a) n is the sum of two fourth-powers (a fourth-power is ##k^4## for some integer k).

Since the constant 0 is not allowed to appear explicitly, the predicate “x = 0” can’t be written directly, but note that it could be expressed in a simple way as: x + x = x. Then the predicate x > y could be expressed

∃w. (y + w = x) ∧ (w ##\neq## 0).

Note that we’ve used “w ##\neq## 0” in this formula, even though it’s technically not allowed. But since “w ##\neq## 0” is equivalent to the allowed formula “¬(w + w = w),” we can use “w ##\neq## 0” with the understanding that it abbreviates the real thing. And now that we’ve shown how to express “x > y,” it’s ok to use it too. (

b) x = 1.

(c) m is a divisor of n (notation: m | n) (

d) n is a prime number (hint: use the predicates from the previous parts)

(e) n is a power of 3.

**2. Homework Equations**

None

I used ##\wedge for AND and \vee for or##.

I personally prefer writing out the word but I wanted to keep it consistent with the question

**3. The Attempt at a Solution**

One thing I'm unclear about is when I have to "define" a new variable. If the question states "x=1" for example, am I correct in that I don't have to define x, but must define anything else I use with a ##\exists{} or \forall{}## symbol?

I personally prefer writing out the word but I wanted to keep it consistent with the question

a)

Since exponentiation is not allowed, I try to do this with just multiplication and addition. I introduce my two arbitrary variables k and l

##\exists{k}\exists{l}. (k*k*k*k+l*l*l*l=n)##

b)

I think I came up with two ways to do this? The first is a two step approach:

Division(x,y) is "given by"

##\exists{w}. (x=wy)##

Then I divide a value by itself,

##\exists{w}. (x=Division(w,w)) \wedge(\neg{(w+w=w)}))##

Is that considered cheating in the world of propositional logic? I had to write this explicitly in one step, my best attempt would be

##\exists{w}. (w=wx)\wedge(\neg(w+w=w))##

c) ##\exists{u} . (n=um)\wedge( \neg(u+u=u))##

if n is 0 the logic will claim m is a factor unless I say that u can't be 0

d)

I'll try to reuse part c and a. The question seems to indicate it's ok to reuse stuff once you've defined it:

##\neg\exists{u}. (##u is divisor of n##) \wedge (u\neq 1 \wedge u\neq n)##

So it's saying there does not exist an u such that: u is a factor of n, and u is not 1 and not n.

e) I think I need to start by accessing the number 3. I also use part b, so that I'm allowed to set something equal to 1

##\exists{a}\exists{b}\exists{c}. (b=ba)\wedge(b\neq0)\wedge(c=a+a+a)##

so c=3.

##\forall{u}. (##u is a divisor of n##) \wedge (u=1 \vee (##c is a divisor of u##))##

my logic is that every factor of n must itself be a divisible by 3, unless that factor is 1.

Last edited: