1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
2answers
38 views

Need help with $(¬p \vee ¬(p\wedge¬q)) \wedge ¬(p \wedge q) ≡¬p$

Hey guys I just need help solving this solution here. Sorry if I didn't type the symbols correctly. My solution so far: $$ (¬p \vee ¬(p\wedge¬q)) \wedge (¬p \vee ¬q)≡ (¬p \vee (¬p \vee q)) \wedge (¬p ...
1
vote
1answer
41 views

Negation of a proposition of the form “not(p) & q”

This is a homework question I'm working on. I think it's right but I'm just curious if I'm supposed to state the negation of "but it is always right" differently. Find the negation of the ...
-3
votes
0answers
23 views

determine the validity of the argument [closed]

Determine the validity of the following argument: If an object is not blue then it is not a triangle. If an object is not above all the black objects, then it is not a square. All ...
0
votes
0answers
33 views

Logical Notations for Descriptive Mathematical Statements

I'm studying Discrete mathematics and I'm faced with a problem of converting a descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a). Any integer ...
0
votes
2answers
134 views

Predicate Logic and Sets (Review Questions)

I have a couple questions I have tried. These are simple homework questions I am doing for review for my 3rd year course in university. These are not for marks. Predicate Question 1) Let the ...
1
vote
1answer
48 views

Logical Notations for Mathematical Statements

I'm studying Discrete mathematics and I'm faced with a problem of converting a few descriptive mathematical statements into logical notation. Any help would be appreciated. Thank you. a). Any divisor ...
1
vote
3answers
68 views

Proving that something is irrational

I'm trying to evaluate the following claim: $$ \sqrt{2} + \sqrt{n} $$ is irrational. This is what I tried: Proof by contrapositive: Suppose $$ r = \sqrt{2} + \sqrt{n} $$ and r is rational. Then $$ ...
1
vote
1answer
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 ...
0
votes
1answer
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. ...
1
vote
1answer
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 ...
1
vote
6answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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 ...
3
votes
2answers
43 views

Could someone explain DeMorgan Laws?

I'm having a bit of trouble visualizing these laws we learned in class today. He mentioned DeMorgan's Law when dealing with Quantifiers, and wrote this on the board: $$\neg \forall x P(x) \iff ...
0
votes
1answer
36 views

Discrete Mathematics - Logic

Let $UH = \{0, 1\}$. For each of the following formulae charaterize their models (tell what needs to be true for the formulae to be true). $\forall X(p(X,0,X))$ $\forall X\exists Y(p(X,Y,0))$ ...
1
vote
1answer
32 views

Express statements using symbolic logic

Consider the predicates $M(x,y):$ "x has sent an email to y", $T(x,y):$ "x has called y". The predicate variable x, y take values in the domain D = {students in the class}. I need to express ...
0
votes
1answer
30 views

Material Implication

I'm working on some problems that demonstrate some simple implications. The logic seems to be very different from the way I'm used to using it in everyday language. I'm not sure what assumptions I am ...
2
votes
2answers
48 views

Is this truth table correct?

Is this truth table correct? Sorry for the formatting Truth table for $p ∧ c$ and $p ∨ c$, with $c$ representing a contradiction: $$\begin{array}{cc|cc} p & c & p∧c&p∨c \\ \hline T ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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) ∧ ~ ...
1
vote
1answer
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$
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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)?
0
votes
2answers
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 ...
1
vote
1answer
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.
0
votes
1answer
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 ...
0
votes
2answers
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.
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
2answers
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.
1
vote
1answer
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)$ ...
5
votes
2answers
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 ...
2
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
1answer
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
2
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
79 views

prenex normal equivalence challenges in math

consider these two following formula are prenex normal equivalence with the above formula? i think yes, but didn't have any idea to explain it.
0
votes
1answer
45 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
0
votes
1answer
125 views

Logic challenge in math

i get stuck in logic problem. suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that ...