Questions concerning predicate calculus, i.e. the logic of quantifiers.

learn more… | top users | synonyms

1
vote
2answers
36 views

Existance of an (in)finite theory having infinite model

Please help me to study the following simple cases: Let $P$ be a binary predicate symbol. I am trying to find out, if there exists a satisfiable $T$ having infinite models only, for the following ...
0
votes
0answers
19 views

Modal Logic translation example

I have an argument that I want to prove is valid, but my repeated failures at this have me worried that I did not translate the argument correctly. Here it is: Necessarily, "The sky is blue and the ...
0
votes
3answers
38 views

How would I translate this sentence into a predicate formula

A dragon is green if at least one of its parents is green I have ∀X⋅dragon(X) ∧ green (X) ⇒ ∃Y⋅childOf(Y,X)∧green(X) Is this correct?
0
votes
0answers
19 views

Where can i learn about propositions, predicates and constructing a truth table?

I need help on where i can learn about propositions, predicates and constructing a truth table and be able to answer questions like this; Represent a statement using propositions, construct a truth ...
0
votes
3answers
28 views

Help with logical quantifiers

Let $L(x,x)$ be "$x$ loves $y$". Then is the statement: "Nobody loves everybody" equivalent to $$∀x ∀y \overline{L(x,y)} $$
0
votes
2answers
22 views

(P and(not(not P or Q))) or( P and Q) equals P

I've been trying to verify the condition above but I get stuck on the passage : $$(P \land (P \land \lnot Q)) \lor (P \land Q)$$ I don't know how to simplify it since there are two ands and a not Q. ...
1
vote
3answers
33 views

Use logic quantifiers to write…

Use logical quantifiers to write: "Everybody loves somebody sometimes" (Where U=all people) I came up with this but not sure how to type symbols in here. $$\forall x \in U\,: \exists y\in U: x \text{ ...
1
vote
1answer
27 views

How to read predicate formulas

I have just started learning about predicate logic and am having some trouble in figuring out how to actually read the formula as as a sentence. ...
2
votes
1answer
12 views

Nested Quantification of exactly one.

Suppose my domain is "All students in the class" and P(x, y):= x has emailed y. So, how do i define: Every student has emailed exactly one student. Exactly one student has emailed every one. A ...
0
votes
1answer
24 views

Propositional Logic with Two Statements

I am given two statements. Letting $s(x)$ denote "$x$ is a car" and $h(x)$ denote "$x$ is manual" I have to formalise the following statements: "Some car is manual" Which I think can be denoted ...
1
vote
0answers
16 views

Do you need quantifiers to formalize an english infinite verb into predicate logic?

I struggle to tranlsate this sentences into predicate logic: 1) To be an intellectual heir of someone is to be taught by that person. 2) To be an intellectual heir of someone is to be taught by an ...
2
votes
1answer
41 views

What is the construct or theory behind the rule concerning the direct proof of a universal statement

Suppose we want to show that $$\forall x\in \mathbb{R}: P(x)$$ is ture for some statement $P(x)$. Since I am taking a matheamtical reasoning class, our textbook provides a "rule of thumb" saying ...
-1
votes
2answers
42 views

What is the denial of a statement in logic math?

I'm trying to get the hang of denials in logic in math. I would like to use these two examples: "Some people are honest and some people are not honest. (All people)" "No one loves everybody. (All ...
0
votes
1answer
24 views

When translating English into quantifiers, when should I use an implication and when should I use a conjunction?

English statement: "Somebody in your class is a zombie." Assuming the domain of x is all people, should this be: $\exists x ( C(x) \land$Z(x)) or $\exists x (C(x) \rightarrow Z(x))$ My guess ...
0
votes
1answer
29 views

Proving inadequacy given a set of connectives

Let $\oplus$ be a binary connective defined by the truth table: $\begin{array} {|r|r|} \hline p &q & p \oplus q\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ ...
0
votes
1answer
29 views

Negation of a statement

What would be the negation of the following statement? "There exist vertices $u$ and $v$ of $G$ such that the edge $x$ is on every path joining $u$ and $v$." Would it be, "there exist vertices $u$ ...
3
votes
0answers
32 views

Negating a predicate with a biconditional

Negate the following statement and make the negation appear immediately before the predicates $$ \forall x \forall y(Q(x,y) \leftrightarrow Q(y,x)) $$ I did the following steps: $$ \neg(\forall x ...
0
votes
0answers
25 views

Assessing Truth Value of Predicate Logic Statements

Consider the following interpretation: Domain = {1, 2} Assignment of constants: a = 1 and b = 2 Assignment of functions: f(1) = 2 and f(2) = 1 Assignment for predicate P: P(1, 1) = T; P(1, 2) = T; ...
1
vote
1answer
89 views

Translating English to Predicate Logic

I need some help translating the following English sentences to predicate logic. I want to make sure I'm doing it correctly. a) Any pet either loves itself or some other person. What I got: ...
1
vote
1answer
39 views

Proof of Why or Why Not some equivalence holds

How do I prove that this equivalence $$\lnot\exists x\,\forall y\,(P(x)\Rightarrow\lnot Q(x,y))\equiv \forall x\,\exists y\,(P(x)\land Q(x,y))$$ holds or not? I remember that $A\implies B\equiv\lnot ...
21
votes
5answers
3k views

Please explain, “Asymmetric is stronger than simply not symmetric”.

In some textbook I found a statement like, "Asymmetric is stronger than simply not symmetric". But as I try to perceive this statement, both appear to be same to me. For example, ...
2
votes
2answers
42 views

nested quantifiers (exactly one questions)

Express this statement using quantifiers, without using the uniqueness quantifier."There is exactly one student in this class who has taken exactly one mathematics class at this school" T (x, ...
0
votes
0answers
14 views

use of venn diagrams to check predicate logic

the logic statements based on multiple quantifiers seem really daunting .Is there a way to verify the validity of such an expression like $$\forall x(P(x)\rightarrow Q(x)) \rightarrow (\forall xP(x) ...
0
votes
0answers
10 views

Exchange the predicate depending on x and y such that the proposition holds for all combinations

∀x ∈ M1 ∃y ∈ M2 : x has to attend lecture y in some semester according to the programme schedule My answer is # ...
2
votes
1answer
44 views

Functor between ordered sets.

(a) Let $f : K \rightarrow L$ be a map of sets, and denote by $f^* : \mathscr{P}(L) \rightarrow \mathscr{P}(K)$ the map sending a subset $S$ of $L$ to its inverse image $f^{-1 }[S] \subseteq K$. ...
0
votes
1answer
25 views

Definition of variables in propositional calculus

Let $\tilde P$ be a first order algebra, and consider the definitions below: I'm confused about the very last thing: what $y\not\in V(c)$ means. $c$ has a free variable, so what does it mean to say ...
1
vote
0answers
34 views

Translate from logical expression to regular expression

I have a type of exercise in which I want to translate a formal logical expression to regular expression. Now my question is, is there a set of rules which I can learn so I will be able to do this ...
0
votes
1answer
33 views

Extension of a theory vs conservative extension

I'm not sure whether I get the difference between extension $T'$ of some theory $T$ and conservative extension $T''$ of this theory. Extension $T'$ of $T$: Language $L\{P\}$ and it's theory $T$ ...
1
vote
2answers
47 views

Can't find a theory which meets conditions

I'm trying to solve this problem. There is a language $L = \{f\}$ with equality (we can use '$=$'), where $f$ is a unary function. Our goal is to decide and prove, whether there is a theory $T$, ...
0
votes
1answer
31 views

Logical translation with possibly one or two premises

I'm trying to translate an argument into sentential logic. It's of the form $$\text{sentence }1:\text{ } p\\\text{sentence }2: \text{ If so, then } q$$ What I want to know is, do I translate this as a ...
0
votes
1answer
38 views

Wording of problem 6. (a) in Chapter 3 of Spivak's Calculus

I've been having difficulty understanding this problem for awhile and figured out why. To clear things up, I just need to understand the logical difference ( if there's no difference, then the problem ...
0
votes
1answer
27 views

Predicate Logic Conclusion

I want to show that $ A \vee B $ is a consequence of $ A \wedge B $. So far I have tried some replacement rules so I could rewrite the premise (which is $ A \wedge B $) but I didn't figured it out.
0
votes
2answers
68 views

Proof by contradiction in predicate logic

So we are given the following to prove, only by proof by contradiction $\forall x(Q(x)\to P(y)) \vDash \forall xQ(x)\to P(y)$ Now the first thing that comes to mind in predicate logic when i am on a ...
0
votes
0answers
26 views

Find a formula for specific evaluation

There is a language $L = \{+, *\}$ with equality. $M$ is implementation of $L$ such that $+$, $*$ are binary functional symbols, standard sum and multiplication, carrier is $N_0$. I am trying to find ...
0
votes
1answer
41 views

How to decide whether a logical formula is satisfiable

I'm trying to solve one logical problem. I have Language L={P} with equality (there can be '='). And we have 4 formulas an theories of this language. We have to ...
0
votes
0answers
24 views

Converting English to predicate logic

Given the following: The domain is X, the set of people. And the functions S(x), meaning that “x has been a student of Course101,” A(x), meaning that “x has gotten an ‘A’ in Course101,” T (x), ...
1
vote
1answer
15 views

Determining validity in predicate logic

Not sure if I've done this correctly. Check the following formulae for validity. If valid, justify why. If they are not valid, give a countermodel. i) ∃xP(x)→∀xP(x) ii) ∀xP(x)→∃xP(x) ...
1
vote
4answers
58 views

Deciding if a statement is true or false for given sets

Given the sets: $A = \{a,b,c\},\enspace B = \{a,b,A,C\},\enspace C = \{a,c\},\enspace D = \{A,B,C\},\enspace and\enspace G = \{A,B,C,D\}$ How can I determine if the following statement is true ...
0
votes
2answers
59 views

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist for these statements

Does function: $ f: \mathbb{Z} \to \mathbb{Z} $ exist, such that this statement is true: $$(\forall{x} \in \mathbb{Z}:f(x) \geq 2)\Rightarrow(\forall{x}\in \mathbb{Z}:f(x)<10)$$ and this statement ...
2
votes
2answers
30 views

Express statement “not every student in this class will pass the Discrete Mathematics”

I have a bit of a problem with this question: Express the following statement using predicate function(s), existential or universal quantifier, and/or negation. “not every student in this ...
1
vote
1answer
43 views

Counterexample for first order logic argument

Find a counterexample to show that the following argument is not valid: ∃xP(x), ∃x(P(x) → Q(x)) |= ∃xQ(x) To my understanding, I have to a select a single element $x$ such that the ...
1
vote
2answers
32 views

Simplify Implication Expression (Predicate/Prop Logic)

I'm trying to do some past paper questions for revision and find myself perplexed on some of the expressions that need normalized/simplified which involves an implies. For example: (A ∧ ¬B) → B ∨ C ∨ ...
0
votes
1answer
33 views

Turn sentence to predicat formula

I am to write this senten "I have read atleast 2 books" into formula of predicat logic where C(x) = i have read x; The only thing i can think of is $(\exists x)\wedge (\exists y)(C(x) \wedge ...
0
votes
1answer
48 views

Natural deduction : $\lnot \forall x.P(x) \to \exists x. \lnot P(x)$

I have to prove in the first predicate logic, using natural deduction, that $\lnot \forall x.P(x) \to \exists x. \lnot P(x)$. Any idea?
0
votes
2answers
44 views

find out if formula is logically true

I have an formula , and i am to find if it is logically true. ((∃x)A ∧ (∃x)B) ⇒ (∃x)(A ∧ B) By definition , to check if it is true , i should neg it and create a semantic tree. But with that it ...
2
votes
1answer
33 views

Using predicate logic to verify the theorems of Euclid's elements?

I wanted to make a "logical" march through the entirety of Euclid's elements by proving and verifying, step by step, each theorem using Hilbert's axioms as a basis. Of course, I would want to do this ...
0
votes
1answer
25 views

How to prove the expressiveness of first-order logic formulas with equality over the empty signature?

How can one prove that every first-order-logic formula with equality over the empty signature is equivalent to either False, or "there are exactly n elements in the domain", or "there are at least n ...
0
votes
2answers
83 views

What's wrong with this natural deduction proof?

According to natural deduction $\forall$ $x$ $\exists$ y $P(x,y)$ $\models$ $\exists$ $x$ $\forall$ y $P(x,y)$ is incorrect. However I am able to prove the following using the rules of natural ...
1
vote
1answer
60 views

Is there a definition of the existential quantifier which does not imply the axiom of choice?

The definition of the existential quantifer given in Bourbaki's Theory of Sets is $$(\exists x)R \iff (\tau_x(R)\mid x)R.$$ Here $x$ is a letter, $R$ is a relation, and $(\tau_x(R)\mid x)R$ means ...
1
vote
0answers
43 views

Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their ...