0
votes
2answers
52 views

Why relations are definied as the smallest

Often relations are definied as follows: The xxxxx relation is the smallest relation satisfying... My question is why relations are defined as the smallest ...
0
votes
2answers
34 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
32 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
63 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
101 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
56 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
45 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
25 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 ...
0
votes
1answer
48 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
78 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
61 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
70 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
42 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
122 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 ...
1
vote
1answer
34 views

Rules of inference: The Rules of Disjunctive Syllogism and Double Negation

I have a question about the use of Double Negation in relation to this problem I found in my textbook examples. Problem: $\;¬(r \land t) \lor u$ $\;r \land t$ Therefore, $u$. In my textbook it ...
0
votes
1answer
35 views

Disjunctive Normal Form (DNF) of a boolean combination

Upon revisiting chapter 1 of Robert S. Wolf's "A tour though mathematical logic" I sumbled upon the following Proposition on page 13 : Suppose that $P$ is a Boolean combination of ...
1
vote
1answer
24 views

predicate logic ,writing in notation form

The statement below should be rewritten in the form “ for all · · · x, · · · .” "No computer scientists are unemployed" Answer Let computer scientists = CS unemployed=U for all x element of CS, x ...
1
vote
1answer
37 views

More questions on quantifiers

I have the following questions: Write the following statements in more abbreviated form, using quantifiers. Here the short phrases “is prime” and “is a line” are allowed, and the symbol $\Pi$ may be ...
0
votes
3answers
26 views

Question on quantifiers

The following question is taken from the Book "Introduction to Mathematical structures and proofs: Let $A = \{1, 2, π\}$, and let $P$ be the statement $x \in A$ and $x \in \Bbb Z.$ Determine the ...
0
votes
3answers
37 views

Translating a sentence into a logical expression.

I am having trouble understanding the solution given for a problem in my discrete mathematics text book. Any help would be much appreciated. Question: Let L(x, y) be the statement "x loves y", where ...
1
vote
1answer
28 views

Manipulating and simplification of Boolean functions

How is the function ((p v (r v q)) ^ ~(~q ^ ~r) is equal to the function (q v r). Can anyone show how is this simplified using formulas asuch as De Morgans ans etc???
1
vote
1answer
50 views

Boolean Functions and using rules ..

Is the function $p \wedge (~\neg(\neg p \vee q) \vee (p \wedge q))$ equal to the function $p \wedge q$? Do I need to provide a truth table for this, or do I have to use the rules (for Manipulating ...
0
votes
2answers
48 views

Using DeMorgan’s rule, state the negation of the statement

Using DeMorgan’s rule, state the negation of the statement: “The car is out of gas or the fuel line is plugged.” Let C stand for “The car is out of gas” and let F stand for “the fuel line is ...
2
votes
2answers
37 views

Using DeMorgan’s rule …

Using DeMorgan’s rule, state the negation of the statement: “Mary is a musician and she plays chess.” Answer Let m stand for “Mary is a musician” and let c stand for “she plays chess”. then the answer ...
0
votes
1answer
41 views

Logic: Binary Relations

A binary relation may be reflexive, irreflexive, or medioreflexive (neither reflexive or irreflexive). Similarly, it can be symmetric, asymmetric, mediosymetric and/or transitive, intransitive, or ...
1
vote
3answers
41 views

Does Disjunctive Syllogism eliminate one premise?

Would the following example be an accurate representation of valid argument that is a disjunctive syllogism? S or not T S Thus, not T My thought process was that ...
0
votes
1answer
52 views

Logical disjunction with sets

I have a question involving sets and logical disjunction, I have no idea of how to go about solving it. The question: A survey of 40 IT users established that: All of them used at least one of ...
1
vote
3answers
72 views

Prove that $A\subseteq B\Longleftrightarrow A\cap B = A$

In set theory logic mathematics. How would i do the proof for: $A\subseteq B\Longleftrightarrow A\cap B = A$
1
vote
1answer
41 views

$(A \lor B) \implies (((A \lor B) \implies A) \lor ((A \lor B) \implies B))$?

Is the implication in the title true? I haven't studied logic formally yet, so I can't precisely say what A, B exactly are. Perhaps "predicates in first-order logic"?
0
votes
1answer
23 views

Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +…+ n(n+1) = n(n+1)(n+2)/3

The problem is :Prove that for all elements n that are member on set N, 0*1 + 1*2 + 2*3 +....+ n(n+1) = n(n+1)(n+2)/3 I have established a base case for n=0, 0*1 = 0(0+1)(0+2)/3 = 0 I have also ...
0
votes
2answers
35 views

Gives regular expressions which defines regular language and what does {1,2} mean

The question is give a regular expression which defines a regular language. Question: The language over {0,1} consisting of all strings which either have length less than 3 or have 0 as their third ...
1
vote
1answer
68 views

$(p \implies q) \wedge (q \implies r) \implies (p \implies r)$

Show that $(p \implies q) \wedge (q \implies r) \implies (p \implies r)$ is a tautology. I have the truth tables but cannot algebraically manipulate the language itself to prove it. What I ...
1
vote
2answers
62 views

How to find the Equivalence class for a given set?

I'm really having trouble understanding these equivalence classes. Could someone please guide me through the following problem step by step, and help explain this. I have a final exam next week, and ...
1
vote
1answer
65 views

Finding Truth Values Of Nested Quantifiers

I'm looking at for example, $∃x∀y,P(x≥y+1)$ I'm told in order to prove that this is true I can us the technique that follows: Find one value of $x∈X$(only needs to be one) that has the property that ...
0
votes
2answers
60 views

What subject in mathematics investigates the type of problems that constitute the LSAT “logic games” (example given)?

For my own curiosity, I read part of an LSAT study guide yesterday. The "logic games" section comprised questions like, An advertising executive must schedule the advertising during a particular ...
1
vote
1answer
57 views

Truth value of conclusion

Here I are premises followed by a conclusion. I want to confirm if my understanding about conclusion being false is right or not. In the book it was mentioned that their conclusion is false. My ...
1
vote
1answer
70 views

How to prove if two propositions are always true

Let P1 and P2 denote the following propositions: P1="CS is difficult or not many students like CS". P2="If math is easy, then CS is not difficult". Suppose that both P1 and P2 are true, determine if ...
0
votes
1answer
36 views

rewriting quantifiers using propostional expressions

Let the domain of the propositional function P(x) be D={a,b,c}. Express the following quantified statements without using quantifiers but as logical expressions of P(a), P(b) and P(c) using AND, OR, ...
0
votes
1answer
43 views

Propositional Logic Proof [closed]

how to prove this statement using propositional logic. The idea is in my head but i just can't seem to figure it out. Here is the statement : (A->B)^(B->(C->D))^(A->(B->C))->(A->D) This is what i've ...
1
vote
0answers
212 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
0
votes
1answer
40 views

Discrete Math Recursive Functions for Strings

Recursive Functions for Strings Construct a recursive definition for the following string function over the alphabet {x,y}: f(x) returns the string where every x is replaced by xy and every y is ...
0
votes
1answer
31 views

Can an element hood test be converted into an existential statement?

I'm just curious whether it makes sense to convert a statement of the form: $$ y\in \{x\in A : \phi(x) \} \;\; \text{into the form} \;\; \exists x(\,...) $$ It's just that in the book I'm reading the ...
0
votes
2answers
56 views

Equivalent logical quantifier statements?

I was doing an exercise that said convert the statement "Jane saw a police officer, and Rodger saw one too" into the logical equivalent using quantifiers. My answer was: $$ \exists x(P(x)\implies ...
1
vote
2answers
78 views

Discrete Maths Logic Question

p = False, q = True and r = False. Is $¬(p∨q)∧(¬p∨r)$ = false? My reasoning: $$(p∨q)=T \text{ as it is (F or T)}$$ but its the negation so $¬(p∨q)=F$? Then, $(¬p∨r)$ as p is F but its the ...
1
vote
4answers
79 views

logic: two simple math contradictions

1.The contradiction of the sentence: - There is a greater number than a million. can be stated as follows: - There is a number which is not greater than a million. 2.and the contradiction of the ...
1
vote
1answer
52 views

How to disjunct $\forall x.(P(x) \lor Q(x)) $

I really don't understand how to disjunct this. The whole argument is: $$\forall x.[P(x) \lor Q(x)] \rightarrow \neg[\exists x.P(x)] \rightarrow \forall x. Q(x) $$ Am I supposed to use the ...
0
votes
1answer
58 views

I'm lost on formally on how to prove

$A \cap B^\complement \subset C \iff A \subset B \cup C$. I could not succeed to go from the left expression to the right, can you please help?
1
vote
1answer
85 views
1
vote
3answers
65 views

Show that “$\Gamma \models S \Rightarrow \Gamma \vdash S$” entails “if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable”

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable" I'm primarily confused with the notation being used here. In ...
0
votes
1answer
62 views

Mathematical Induction for greedy algorithm problem?

Suppose you want to place towers along a straight road, so that every building on the road receives cellular service. Assume that a building receives cellular service if it is within one mile of a ...