# Tagged Questions

28 views

### Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
30 views

### Trying to wrap my head around the idea of Proving Rule of Cases is a valid arument

I had a question on my assignment today that asked to "Prove that the Rule of Proof by Cases is a valid argument." Based of what I've read, Proof by Cases is valid when all cases produce the same ...
35 views

### Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ (in a Boolean algebra)

Suppose X is a Boolean algebra. Prove that: if $x \sqcup \bar{y}=1$, then $x \sqcup y=x$ I suspect this one is not that difficult, but for some reason I can't find the answer. This homework ...
78 views

### Predicate Logic and Logic Proofs(Review & Homework Questions)

I'm working on some homework questions and I am struggling very hard with the logic proofs. I might have an incorrect answer for 1 of the predicate questions but I think my question makes some sort of ...
38 views

22 views

### Need help with proving conditionals

Suppose P(x) is the assertion that "x is odd" and Q(x) is the assertion that "x^2 - 1 is divisible by 8" For part A it wanted us to prove P(x) -> Q(x). I solved that one but I'm having trouble ...
18 views

### How to prove a statement with multiple conditionals

Suppose I have a claim to prove: If x and y are distinct real numbers, then $$(x+1)^2=(y+1)^2$$ iff $$x+y = -2$$ $$\n$$ In order to solve this do I tackle the if and only if part first? i.e. ...
21 views

### Logic for implications

Example statement: Suppose we have a statement like : (P)Let S be a set... if (Q){other stuff} So I was wondering what the example statement refers to exactly. Is it Q -> P? Because Q comes after ...
52 views

### I'm not sure what this is exactly asking

Without using words of negation, write the meaning of : "f is not an increasing function" I did: $$"f\ is\ not\ an\ increasing\ function" \ \equiv\ "f\ is\ a\ decreasing\ function"$$ Is this what ...
22 views

### Are the negations of these statements correct?

If today is New Year's Eve, then tomorrow is January. Negation: Today is New Year's Eve and tomorrow is not January. If y is non negative, then y is positive or y is 0. Negation: Y is not a non ...
26 views

### How can I use these logical equivalences to rewrite this sentence?

Here are the logical equivalences: $p \rightarrow q \vee r$ $p \wedge \lnot q \rightarrow r$ $p \wedge \lnot r \rightarrow q$ Sentence: If $c$ is prime, then $c$ is odd or $c$ is $2$. How can I ...
48 views

### How can I use modus ponens or modus tollens to produce valid arguments? [closed]

I know this one is: $(1)$ If logic is easy, then I am a monkey’s uncle. I am not a monkey’s uncle. ∴ ? My answer: $\therefore$ Logic is not easy. (2) Can someone help me with this one? If ...
43 views

31 views

### How can I simplify and verify the logical equivalence using these laws?

∼(p ∨∼q) ∨ (∼p ^ ~ q) ≡ ~p Please help I don't know where to start. These are the laws I need to list in each step when simplifying. Commutative laws: p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p Associative ...
43 views

### How can logical equivalence be derived from this..

(p ∨∼q) ∧ (∼p ∨∼q) ≡ (∼q ∨ p) ∧ (∼q ∨∼p) by (a) ≡∼q ∨ (p ∧∼p) by (b) ≡∼q ∨ c by (c) ≡∼q by (d) Therefore, (p ∨∼q) ∧ (∼p ...
21 views

### Creating statements using symbols

Are these statements correct? And can anyone help me figure out letter c? Let h = Joe is healthy, w = Joe is wealthy, s = Joe is wise. a. Joe is healthy and wealthy but not wise. Answer: (h∧w) ∧ ~ ...
22 views

### Are these statements negated correctly using De Morgan's laws?

$-10 < x < 2$. Negation: $-10 \geq x$ or $x \geq 2$. $x \leq -1 \text{ or } x > 1$ Negation: $-1 > x \leq 1$
38 views

### How can I write negations for this statement?

Are these negations correct using De Morgan's laws for this statement: This computer program has a logical error in the first ten lines or it is being run with an incomplete data set. Negation: This ...
59 views

### Show that this argument is valid.

¬p → C; ∴ p. Where C denotes a contradiction. What does it mean by ¬p → C;? Also another statement ¬p → F; ∴ p. Is there any differences between the two statement since from my understanding a ...
45 views

### Is this a valid proof of $(A∧B’) ∧C↔(A∧C) ∧B’$?

So I am supposed to prove $(A∧B’) ∧C↔(A∧C) ∧B’$ using wffs and equivalence rules. I have never done such proof, and I want to check if my steps are correct. This assignment is only graded based off of ...
29 views

### How do I write this statement using symbols?

Juan is a math major but not a computer science major. (m= "Juan is a math major.", c= "Juan is a computer science major.") How do I write this is symbolic form using the letters and (and, or, not)?
27 views

### Sorting out logic homework with a friend.

My friend and I were looking over my homework and he pointed out something that he thought was incorrect. I was to write sentances using logical connectives. The original sentance was: "To get ...
40 views

### Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
34 views

### Translating to English: $\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$

$$\forall x ¬(\forall y P(x, y)) \rightarrow \forall x \forall y ¬P(x, y)$$ I'm trying to intuitively understand this idea by thinking about it in terms of English. The second half is easy. Where P ...
40 views

### What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
45 views

### Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
94 views

### Why relations are defined as the smallest

Often relations are defined as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
42 views

### Let Alphabet have only one unary function of symbol f. Prove that every term must have 3K+1 symbols for some k≥0.

I believe in order to solve this question, I have to perform induction on the complexity of terms. But I'm not sure how to begin.
43 views

### How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
72 views

### Alternate translation for: “Every real number except zero has a multiplicative inverse.”

A given text states, “Every real number except zero has a multiplicative inverse" (where mul- tiplicative inverse of a real number x is a real number y such that xy = 1). It offers the following ...
111 views

### About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
62 views

### Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
48 views

### prenex equivalence problem

Suppose: $$\forall x\exists y \phi(x,y) \to \neg \exists x\psi(x)$$ which of the following formula are prenex normal equivalence with the above formula? i didn't any idea to explain it. it's a ...
28 views

### Either or in compound statement

I think this might be a silly question, but I'm confused. Please help me to understand it. Statement is: Randy studies German on either Tuesday or Friday. How should I write this as compound ...
55 views

### Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
88 views

### First Order Logic Consistency Big Problem

as i read some tutorial material on First Order Logic, i deduce that the following formula was consistent in FOL except the third one. am i right? i have doubt about the first one. any idea? thanks to ...
63 views

### TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...