Questions about logic and mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

0
votes
2answers
49 views

Trying to understand negation of quantifiers

Trying to understand the negation of the following: For this: ∀x~P(x) I have this as negation: ~∃xP(x) For this: ~∃x(∀yP(y) Λ Q(x)) I have this: ∀x(~∃yP(y) V ~Q(x)) Are these correct? If not please ...
2
votes
1answer
42 views

Negating statements

I have midterm exam tomorrow, and I am having trouble in negating statements. Am I right? I have to negate the following statements: For every positive integer a, there exists an integer b with ...
0
votes
1answer
53 views

Find all the prime implicants for the following Boolean functions, and determine which are essential.

Find all the prime implicants for the following Boolean functions, and determine which are essential: F(W,X,Y,Z) = Im(0,2,5,7,8,10,12,13,14,15) Book solution: Prime = XZ, WX, X'Z', WZ' Essential = ...
1
vote
1answer
85 views

Proof using existential quantifier [closed]

Prove: $$\begin{align} \exists x ~:~ \bigg(p(x) &\rightarrow q(x)\bigg) \ How do I go about proving this? Can I distribute the existential quantifier in the first term?
3
votes
0answers
111 views

indices set and halting problem in computation course

I ran into a multiple choice question that confused me with this notation. anyone could help me? this is adapted from an old class quiz in Calgary. Suppose A is be indices (i think index set) of type ...
2
votes
2answers
93 views

Are higher order logics substantially stronger than second order

Do we get much by using logics of order higher that 2? Does each transition to next level provides much power?
1
vote
2answers
55 views

Direct proof (Logic)

I need help, I've to give by resolution a direct proof of I've made a conjunction and got: How do I give a direct proof by resolution?
0
votes
1answer
35 views

Which of these sentences are propositions? What are the truth values of those that are propositions?

Which of these sentences are propositions? What are the truth values of those that are propositions? a) Boston is the capital of Massachusetts. b) Miami is the capital of Florida. c) 2 + 3 = 5. d) 5 + ...
1
vote
1answer
33 views

Find $\{x\in \mathbb R\colon\neg(3x>21\implies x\leq 5) \}$

For which $x\in\mathbb{R}$ does $\neg(3x>21\implies x\leq 5)$ hold? I believe it holds for all $x>7$, but I don't know how to formally write this down. Can someone help me out? Is there a ...
2
votes
1answer
32 views

Non-decidable $\Pi^0_1$ (effectively closed) classes

Are there non-decidable $\Pi^0_1$ (effectively closed) classes? According to a draft of Effectively closed sets by Cenzer and Remmel, the class $$ P = \{ 0^n1^\omega \mid n \in B\} $$ is a ...
1
vote
1answer
45 views

In Whitehead & Russell's PM, if $P$ is an infinite well-ordered series, can $P$ have a last term?

If I'm not mistaken, $B‘\overset{\smile}{P}$ is the last term of $P$. If it does not exist, there is no need to put ~$(B‘\overset{\smile}{P}) \in C‘∇‘P $ in the hypothesis. Chances are I missed ...
0
votes
1answer
58 views

Difference between type and similarity type

In usual terminology, is there a difference between the type and similarity type? Is there a general consensus for the definition of the two terms? Please suggest to me books where I can study these ...
-1
votes
0answers
39 views

Discrete mathematics - predicate statements equivalency

Indicate whether or not the two statements are equivalent. Explain in a few words why the statements are equivalent or provide an interpretation under which one is true and the other is false. ...
1
vote
0answers
40 views

Predicate logic. Check if I have done this correctly

I need someone to verify if I have translated a sentence into predicate logic correctly. Given predicates: Empty(x) : the list x is empty Sorted(x) : the list x is sorted in ascending (not ...
2
votes
3answers
62 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
0
votes
1answer
28 views

Question about logic simplification

If I had to simplify ~(p^q)v~(~p^q) so first I would distribute and get: (~pV~q) v (pv~q) After distributing can I drop the parentheses and combine? What would be the next step in simplifying?
1
vote
1answer
43 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
6
votes
0answers
80 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
1
vote
1answer
51 views

Is this assertion true or false? $(\exists x)(\exists y)(\forall z)(y \ne x+z \Rightarrow y\lt x)$ Cohn - Classic Algebra P7

$x,y,z\in\mathbb{N}$ with $0$ $(\forall x)(\forall y)(\exists z)(y \geq x \Rightarrow y=x+z)$ Can you help me with trivial thing above? I imagine it is because I am tired, but I can't see if this is ...
0
votes
0answers
19 views

How to express this set in terms of the given three sets? [duplicate]

Given the sets $A$, $B$, and $C$, let the set $D$ be defined as follows: $$ D \colon= \{ x | \, x \in A \, \land \, (x \in B \implies x \in C) \, \}.$$ Then how to express the set $D$ in terms of ...
2
votes
3answers
107 views

In Whitehead & Russell's PM, does every Series contain a $P_1$ (immedeately precedes)?

✳204.7 $\vdash: P \in Ser .\supset. P_1 \in 1 \rightarrow 1$ Which says if $P$ is a series, then $P_1$ is one-one. ✳201.63 $\vdash: P \in trans \cap Rl‘J .\supset. P_1 = P \overset{.}{-}P^2$ ...
0
votes
2answers
47 views

Resolution Refutation

I am solving a few questions to better understand the way resolution works and now i've come across this question which has no explicit conclusion and I am supposed to use 'Resolution Refutation' to a ...
0
votes
2answers
43 views

Are there multiple contrapositives?

Are there "multiple contrapositives"? Normally a contrapositive from P implies Q changes to not Q implies not P. Secondly, can a contrapositive be in the from of P in the antecedent and Q be the ...
-1
votes
2answers
35 views

Negation, Converse, or contrapositive?

S: Every employee who is honest and persistent is successful or bored. Would this statement be the negations, converse, or contrapositive of S? -> All employees who are dishonest or not persistent ...
0
votes
0answers
28 views

Existential quantifier with implication/conjunction as a Venn diagram?

I'm having trouble visualizing the following statements in a Venn diagram: $$\exists x\in D, Q(x) \implies P(x) $$ $$\exists x\in D, Q(x) \wedge P(x) $$ For the first statement, does it look like ...
1
vote
1answer
45 views

Stuck on First-Order Logic

I'm taking a first-order logic class and I keep finding myself stuck on proofs that ask for disjunction elimination and then supply additional premises with conjunctions. How can I eliminate negations ...
1
vote
2answers
23 views

Combination problem with distributing

I've been trying to do last exercise, but I can't figure out method to solve it. I read a book and searched for it in the internet, but I couldn't find exactly what I am looking for. Could you guys ...
1
vote
1answer
55 views

Is there any way how I can use Mathematica in Introduction Logic course?

I am very new comer to Wolfram Mathematica software tool and I am interesting is there any way how I can apply this tool for Introductory Logic course. I am participating at the course on 'coursera' ...
2
votes
1answer
45 views

Conjunctive Normal Form

Is a statement of the form $\phi \vee \psi \vee \xi$ considered to be in its conjuntive normal form (CNF), given that $\phi \vee \psi$ is considered to be in CNF? Example: While converting $\phi ...
0
votes
1answer
41 views

Predicate logic, translate sentence

I need help with how to translate a sentence into predicate logic. It would also be nice if you could have a look at another one that I have solved, if it is correctly solved Given predicates: ...
2
votes
6answers
131 views

Prove that A = B if and only if A $\subseteq$ B and B $\subseteq$ A

I want to prove that $A = B$ iff $A \subseteq B$ and $B \subseteq A$. I'm unsure of how to approach this problem. It seems really easy but I have no idea. Help would be greatly appreciated.
0
votes
1answer
37 views

Am I on the right track simplifying this logical expression?

I am just learning logic and sets, and I am not completely familiar with them yet, that's why I am asking you here, if at least I am on the right track. Is this first of all correctly simplified? ...
2
votes
5answers
90 views

Mathematical logic and contrapositives.

I have the following statement If $x^2=4$, then $x=2$ or $x=-2$ I have to write its corresponding contrapositive. I know that this should be stated as follows: If $x$ is not equal to $2$ ...
3
votes
2answers
97 views

predicate quantifier

a)There is a tree in the back yard. b)If the tree in the back yard is an elm or an oak, then the treasure is in the kitchen and not in the garage. c)If this house is made of bricks or the tree in ...
3
votes
2answers
64 views

Finite list of axioms of $\mathsf{ACA}_0$ - reference?

It seems to be common knowledge that $\mathsf{ACA}_0$ can be finitely axiomatized, see for example Can a finite axiomatization of PA be expressed in a finitely axiomatizable first order set theory? ...
1
vote
1answer
33 views

First-Order Logic: semantic entailment and disjunction

In First-Order Logic, we consider that $\Sigma$ is a set of well-formed formulas (wff), and $\alpha$, $\beta$ are such wff. I would like to prove/disprove the following two statements: If either ...
-2
votes
1answer
44 views

State the value of x after the statement [closed]

State the value of x after the statement if P(x) then x := 1 is executed, where P(x) is the statement “x > 1,” if the value of x when this statement is reached is x = 0. x = 1. x = 2. this answer ...
0
votes
1answer
44 views

Proving property for all predicates in first order logic

Let's consider language with predicate $P$ and following derivation $${{{[P[a/x]]^1} \over {P[a/x] \rightarrow P[a/x]}}\rightarrow I^1 \over {\forall_x (P(x) \rightarrow P(x))}}\forall I$$ Doesn't ...
1
vote
1answer
30 views

a function to specify arity— what do these sentences mean??

I have encountered a function $\pi$ mapping the set of function and predicate symbols to the natural numbers so that for each $k\ge1$, each of the sets {$i \in N | \pi (F_i)=k$}, {$i \in ...
1
vote
1answer
37 views

Give a useful written negation of the statement

I am struggling a bit with giving the useful negation and the written statement: For (b) below: (i) Assign a universal set to each variable, label each component statement with a symbol; (ii) write ...
2
votes
1answer
55 views

Show that: $\sum \models p_1 \lor p_2 \lor … \lor p_n$ for some $n\in \mathbb{N}$

The question states: Suppose that, for each $i \in \mathbb{N}$, $p_i$ is a propositional variable. Let $\sum$ be a set of sentences of the propositional calculus . Suppose that all truth assignments ...
0
votes
1answer
40 views

The relation between equivalence and tautology [closed]

Is the formula $p \leftrightarrow q$ a tautology? Thanks for any insight.
-1
votes
2answers
106 views

What is a mathematical statement? [closed]

What is a mathematical statement? And what makes a mathematical statement different from another mathematical statement? For example, is "$2^3=7$" a different statement than "$2\times(2\times2)=7$"?
2
votes
1answer
44 views

Show that are logically equivalent [duplicate]

Show that are logically equivalent (without truth table) (p → r) ∧ (q → r) and (p ∨ q) → r My solution: ...
0
votes
2answers
25 views

How to transform the following logical expression into English

I don't fully understand the semantics of changing logical expressions into English Transform the following predicate calculus statements into English. Let $A(x)$ represent the statement that $x$ is ...
1
vote
2answers
45 views

Determine whether {¬q∧(p→q)}→¬p is tautology

Determine whether $\{¬q∧(p→q)\}→¬p$ is tautology . this my solution : \begin{align} \{¬q∧(p→q)\}→¬p & ≡¬\{¬q∧(¬p∨q)\}∨¬p \\ &≡q∨(p∧¬q)∨¬p≡(q∨p)∧(¬q∨¬p) \\ &≡(q∨¬q)∧(p∨¬p) ≡T∧ T \\ ...
0
votes
2answers
64 views

How to simplify these identities?

I have to verfiy the following identities $(A \bigtriangleup B) \cup C = (A \cup C) \bigtriangleup (B \setminus C)$ using logic symbols, I have to say what it means to be an element of each set and ...
0
votes
3answers
60 views

Problem understanding why $P \implies (Q \implies P) \equiv T$

I've been through the truth table and I can see how it works but I can't exactly understand why. The proof presented in the book (Logical Reasoning: A First Course by Nederpelt and Kamareddine) says ...
0
votes
4answers
88 views

Translate these statements into English

Translate the following statements into English, where $C(x)$ means '$x$ is a comedian', $F(x)$ means '$x$ is funny' and the domain consists of all people: a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x)) c) ...
6
votes
4answers
1k views

There exist no integers for which $x^2-4y=2$

I am working on a new exercise in my textbook: $$\text{Prove that: (P): }\;\nexists \;x,y \in \mathbb{Z}, x^2-4\cdot y = 2 $$ I am stuck and I would really like to see a correct proof so I can move ...