Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

4
votes
0answers
75 views

(Co)homology of propositional logic

Sorry if this is a rather vague question, but it seemed like something that might be interesting. Let $P$ be a family of propositions, and let $\mathcal L(P)$ be the set of all compound propositions ...
4
votes
0answers
343 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of $G$ corresponds to a state $q$ belonging to a set $Q$ of the state of the Automaton, for $q$ with $\delta(q,a)=q_1*q_2$, the node is ...
3
votes
0answers
73 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
3
votes
0answers
87 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
3
votes
0answers
242 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
3
votes
0answers
73 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
2
votes
0answers
26 views

n-formula for k n-evaluations

I am trying to solve the following problem Let $N = \{0, 1, 2, ...\} $ is the set of natural numbers. Propositional variables are $ A_{n}$ for $n \in N $ . An evaluation $v$ is called ...
2
votes
0answers
71 views

Implication, conjunction and disjunction distributivity problems

I have proven using theorems that implication is left distributive over conjunction: x → (y ∧ z) ≡ ( x → y ) ∧ ( x → z ) Proof: x → (y ∧ z) = ¬x ∨ ( y ∧ z ) = ( ¬x ∨ y ) ∧ ( ¬x ∨ z ) = ( x → ...
2
votes
0answers
24 views

Can an equation be shown to be valid through logic over an continuous range?

I may be asking the impossible - but would appreciate it if someone else were to confirm this for me, rather than me just thinking this... I have a black box function, $f(x)$ that I don't know ...
2
votes
0answers
63 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
2
votes
0answers
80 views

Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
2
votes
0answers
67 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
99 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
1
vote
0answers
16 views

How to solve this equation using semantic equivlence

Hi I am trying to workout the solution to this propositional logic formula using the below semantic equivalence formula but I am stuck. Could someone please help me out. These are the rules ...
1
vote
0answers
22 views

Question in regards to representing propositons with P/~P

In a standard Frege-System does it break any rules to have 'P' stand for, say "Smith is not president"? Is it mandatory that such a statement be represented by '~P', or can it indeed be represented ...
1
vote
0answers
34 views

Soundness of Propositional Logic proof.

Let $$\begin{align} A1&=(p\implies (q\implies p)) \\ A2&=(((p\implies (q \implies r)) \implies ((p\implies q)\implies (p\implies r))) \\ A3&=((\neg p \implies \neg q ) \implies ((\neg p ...
1
vote
0answers
23 views

“Relative unsatisfiability” of SAT instances

There's a natural way to view any SAT instance as a variety: just replace the Boolean algebra $2$ of truth values with the corresponding Boolean ring $\mathbb{Z}/2\mathbb{Z}$. (See my answer to Is ...
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 ...
1
vote
0answers
54 views

Is propositional logic enough to study real analysis?

Is it necessary to study relational logic before starting real anylisis(from Bartle and Scherbert) or propositional logic enough? Also for topics like topology and differential geometry is ...
1
vote
0answers
19 views

Converting equivalence to CNF

I have the following scenario which I need to represent in CNF: we have $n$ bins, and $A_{ij}$ holds iff balls $i$ and $j$ are in a consecutive pair of bins such that the first bin of the pair is ...
1
vote
0answers
28 views

Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions

Show that the truth function $h$ determined by $(A \lor B) \implies \neg C$ generates all truth functions. Could someone explain how I would go about proving this, or how I would start? I am having a ...
1
vote
0answers
41 views

Satisfiability and validity algorithms?

Any tips for how to go about this? "Assume you have an algorithm A available, that when input with a propositional formula F, shows whether F is satisfiable or unsatisfiable. Construct an ...
1
vote
0answers
40 views

how to determine if formula satisfies without creating a truth table

$(p \wedge q \wedge r) \wedge (\neg p \vee r)$ So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p ...
1
vote
0answers
9 views

Truth of propositional formula (dependence on variable)

Identify the correct statements about $2^n\ge100$. The choices are: This is a proposition This is not a proposition Its truth value depends on the value of $n$ Its truth value ...
1
vote
0answers
44 views

Does a Length Always Exist such that a Tautology Always Exists Beyond That Length?

Suppose we have some set of fixed connectives such that tautologies exist and we write everything in Polish notation. The length of a WFF consists of the number of symbols that it has. WFFs can get ...
1
vote
0answers
49 views

Proving strong completeness of propositional logic by assuming weak completeness via algebraic methods.

In logic via algebra (page $93$), Halmos tries to prove strong completeness ( if $S\models q$ then $S\vdash q$) assuming weak completeness ( if $q$ is a valid in the Boolean logic $(A,F)$ then $q\in ...
1
vote
0answers
35 views

Construct theory with a condition

I would need some help here. I'm preparing for finals from mathematical logic and as I am browsing through some exercises, I often found these types: Let's say we have 2 propositions $\phi$ and ...
1
vote
0answers
346 views

Translation of English statements to logical expression using nested quantifier and predicates.

I have come across few doubts solving Exercise of Propositional logic and predicates. Here are they, Doubt 1 ...
1
vote
0answers
39 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
1
vote
0answers
33 views

Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...
1
vote
0answers
114 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
0answers
33 views

Translation into the propositional logic

How could the following sentence be translated into the propositional logic? Since I am here I talk to you. Do I have to use implication like p -> q?
1
vote
0answers
34 views

Validity of Induction Proof - $\{ \land, \top, \bot \}$ is an incomplete set of connectives

I need to verify a proof of the fact that $\{ \land, \top, \bot \}$ is not complete. I consider $\top$ and $\bot$ to be $0$-ary logical connectives that are constantly true or false. That is ...
1
vote
0answers
159 views

Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ ...
1
vote
0answers
219 views

Maximally Consistent Set (Proof by Contradiction)

Yesterday, I asked about feedback for a proof of the following theorem For all $\phi$, $\phi \in \Gamma^{*}$ if and only if $\Gamma^{*} \vdash \phi$. My main concern was the first part $(\to)$, which ...
1
vote
0answers
407 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
0
votes
0answers
20 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
0answers
13 views

Find algebraic normal form that's derived from 2 other ANF

I have to find the ANF of a function $h$ where $h = f \star g$ where $x \star y := x \wedge \neg y$. $f$ and $g$ are given functions. They are $f(x, y, z) = y \oplus x \oplus xy \oplus zy \oplus zx ...
0
votes
0answers
109 views

Is the establishment of the validity of this argument correct?

I am trying to show that the following argument is valid. There is an email that is sent but it is not saved in the inbox. All emails are saved in the inbox or the inbox is full. If the inbox is ...
0
votes
0answers
34 views

compactness theorem failure - An example

Let S be a set of sets of natural numbers. Define S to be "good", if every $A_i \in S$ has $x_i \in A$ s.t. for every $A_1,A_2,A_3 \in S$ it holds $x_1+x_2+x_3 \not\equiv 0 \mod10$. We have to show ...
0
votes
0answers
29 views

How to apply Rules of inference

I know the definition for Rules of inference "A rule of inference is a general pattern that allows us to draw some new conclusion from a set of given ...
0
votes
0answers
83 views

Which of the following statements is always TRUE?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? $\left(\left(\forall x \left(P\left(x\right) \vee Q\left(x\right)\right)\right)\right) \implies ...
0
votes
0answers
22 views

Find truth value of propositional function

I have this propositional function: $p(x,y):y-x=y+x^2$ and I have to find truth value for: $\forall{x}\exists{y}$ $p(x,y)$ $\exists{y}\forall{x}$ $p(x,y)$ Set of all numbers is integer ...
0
votes
0answers
31 views

How to derive this equivalence in propositional logic (Xv!X)->(X->Z)v(Z->X)

I have no special skills of doing this. Can you introduce how to think of that ? I could take Xv!X as hip and then proof by parts x -> (X->Z)v(Z->X). But is the best way always to split disjunction ...
0
votes
0answers
20 views

Conversion into prenex conjunctive normal form

I'm trying to convert $\forall x \exists y(P(x, y) \rightarrow (\neg\exists z \exists yR(z, y) \wedge \neg\forall xS(x)))$ into PCNF, but am getting stuck at the end. $\equiv \forall x \exists y(\neg ...
0
votes
0answers
47 views

Given (p∨r),(¬q∨r), use the Fitch system to prove (p → q) → r

I am trying, given (p∨r),(¬q∨r) to use the Fitch System in order to prove (p → q) → r). Any ideas on how I should proceed?
0
votes
0answers
25 views

L-structure first order problems on groups

Let L ={.,e} where . is a binary function symbol and e is a constant symbol. Write down some fi rst-order L-sentences with the property that, for every L-structure G = (G; I), if your sentences are ...
0
votes
0answers
29 views

Construct the formal proof of validity for the given argument

This is the construction that I need to validate. 1. $\neg(E \vee \neg F)$ 2. $F \Rightarrow G$ $\vdash G \vee \neg E$
0
votes
0answers
22 views

Relations and quantifiers

When talking about relations, we know that the relation is anti-symmetric if "for all x: for all y: R(x,y) AND R(y,x) IMPLIES (x=y)". But can i rewrite this as "for all x: for all y: R(x,y) EXCLUSIVE ...
0
votes
0answers
32 views

intuitionistic logic and propositional logic equation

Show that for propositional logic: $\vdash_i \neg \phi \Leftrightarrow \vdash_c \neg \phi$. How can I solve this?