Mathematics desk
< September 25	<< Aug \| September \| Oct >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 26

Mathematics for Computer Science - Propositional Functions

Suppose the domain of the propositional function P(x,y) consists of pairs x and y, where x = 1, 2, or 3, and y = 1, 2, or 3. Write out the following proposition using disjunctions and conjunctions only:

∃xP(x,y)

I don't even know where to start... (x ∧ y) ∨ (y ∧ x) type thing is what the question is asking for? Because I don't see what that would mean anyway, so any help would be greatly appreciated.

Kidoooo$ (talk) 00:21, 26 September 2018 (UTC)[reply]

I think the kind of expression they have in mind is something like

P(1,1) ∨ (P(1,3) ∧ P(2,3))

That's not the answer, but it's in the general form the answer would take so hopefully that will get you started.

I'm a bit confused though since ∃xP(x,y) has a free variable y, so it defines a propositional function rather than a proposition. Either there is a typo somewhere, or your text/prof is using nonstandard terminology, or the terminology I'm used to is nonstandard (or a combination of these). So maybe the answer is supposed to involve expressions like P(2,y). --RDBury (talk) 05:42, 26 September 2018 (UTC)[reply]

They may mean for all y there exists an x such that P(x,y). However given just what is here I would assume they meant y to be a free variable. You could do both. Dmcq (talk) 19:47, 26 September 2018 (UTC)[reply]

Sorry, there actually was a typo. I meant ∃xP(x,3) Kidoooo$ (talk) 22:21, 26 September 2018 (UTC)[reply]

I also wanted to clarify something about De Morgan's laws. One of them states ¬(p ∧ q) ≡ ¬p ∨ ¬q . Does that also apply to three propositions p, q, and r for example? Like ¬(p ∧ q ∧ r) ≡ ¬p ∨ ¬q ∨ ¬r Kidoooo$ (talk) 23:59, 26 September 2018 (UTC)[reply]

Well, it's true, and it follows from De Morgan's laws. Literally speaking, it's not one of De Morgan's laws, but it's easily derivable from one (plus ~~transitivity~~ associativity of disjunction). --Trovatore (talk) 00:33, 27 September 2018 (UTC)[reply]

I appreciate all of your answers and comments that are helping me understand the material. I also wanted to know if the way I did this is valid or correct:

Suppose the domain of the propositional function P(x, y) consists of pairs x and y, where x = 1, 2, or 3, and y = 1, 2, or 3. Write out the propositions below using disjunctions and conjunctions only.

∃x∀y¬P(x, y)

The above is equivalent to ¬(∀x∃yP(x,y)) So can I write (∀x∃yP(x,y)) using disjunctions and conjunctions and then further adjust it with the negation?

¬(∀x∃yP(x,y)) ≡ ¬((P(1,1) ∨ P(1,2) ∨ P(1,3)) ∧ (P(2,1) ∨ P(2,2) ∨ P(2,3)) ∧ (P(3,1) ∨ P(3,2) ∨ P(3,3))) ≡ ¬(P(1,1) ∨ P(1,2) ∨ P(1,3)) ∨ ¬(P(2,1) ∨ P(2,2) ∨ P(2,3)) ∨ ¬(P(3,1) ∨ P(3,2) ∨ P(3,3)) ≡ (¬P(1,1) ∧ ¬P(1,2) ∧ ¬P(1,3)) ∨ (¬P(2,1) ∧ ¬P(2,2) ∧ ¬P(2,3)) ∨ (¬P(3,1) ∧ ¬P(3,2) ∧ ¬P(3,3))

Is that a valid method and correct answer? Thanks in advance. Kidoooo$ (talk) 02:41, 27 September 2018 (UTC)[reply]

Yes. I'd have just done it direct but no harm some extra exercise, or perhaps they wanted you to do that. Dmcq (talk) 13:50, 28 September 2018 (UTC)[reply]