Desde Estados Unidos, donde viviría y enseñaría hasta su muerte, influyó en toda la investigación lógica posterior a la Segunda Guerra Mundial.

En los años 40 Tarski comenzó a desarrollar junto a sus discípulos el álgebra relacional, en la que pueden expresarse tanto la teoría axiomática de conjuntos como la aritmética de Peano.

El primer acercamiento de Tarski a la noción de consecuencia lógica fue axiomático: la noción quedaría definida por axiomas referidos a la derivación en un cálculo lógico.

Para que la definición se aplique a todos los casos basta con admitir como constantes lógicas, según Tarski, las siguientes: el cuantificador universal de primer orden, el condicional, la negación, los paréntesis y la identidad.

El problema le ocupó durante toda su vida académica; al final de ésta propuso, junto a Steven Givant, una definición en dos partes: En 1933 Tarski publicó en polaco un artículo sobre su definición matemática de la verdad para lenguajes formales.

La influyente traducción al alemán se editó en 1936 bajo el título Der Wahrheitsbegriff in den Sprachen der deduktiven Disziplinen ("El concepto de verdad en los lenguajes de las disciplinas deductivas"), y en 1956 se dio a conocer la versión inglesa como un capítulo de la antología Logic, Semantics, Metamathematics (1956).

Más en general, podría decirse que es ocioso preocuparse por lo que tradicionalmente se ha llamado "verdad" —Adaequatio intellectus et rei[1]​ ("Correspondencia entre el intelecto y la realidad")—: la ciencia ofrece procedimientos para demostrar o comprobar enunciados, y decir 'verdadero' sería una forma arcaica o redundante de decir 'demostrado' o 'probado'.

Pero las limitaciones de los formalismos, que Tarski contribuyó a descubrir en los años 30 —junto a Gödel, Alonzo Church y otros—, mostraban que para avanzar en matemáticas era necesario interpretar (en un modelo) los símbolos del lenguaje de los cálculos lógicos —por ejemplo, para obtener demostraciones de consistencia de un sistema formal relativas a otro, una vez que se demostró que la demostración absoluta es imposible—.

Más precisa le resultaba, sin ser completamente adecuada, la concepción de Aristóteles: .

Por otro lado, Tarski mostró cómo la preservación de ese concepto clásico requería no definirlo para cualquier lenguaje —o para un lenguaje ‘genuino’ al que serían traducibles todos los demás—, sino para lenguajes formales (de fórmulas) interpretables en dominios restringidos: si la concepción clásica se aplica a lenguajes que se refieren ilimitadamente a sí mismos —por ejemplo, la lengua nativa del teórico o de su lector humano— se hace posible caer en contradicciones como la paradoja del mentiroso.

[2]​ Puede decirse que Tarski mostró cómo la concepción clásica sirve para avanzar desde los formalismos, y cómo los formalismos sirven para avanzar desde la concepción clásica, haciéndola más precisa y científica.

No es una implicación tan trivial como puede parecer: el enunciado a la izquierda de “si y solo si” trata sobre la expresión “La nieve es blanca” mientras que el enunciado a la derecha trata sobre la nieve.

Esto último da la pauta al hablante castellano -con una teoría de lo verdadero en inglés- para saber si lo que ha dicho cierto inglés -"The snow is white"- es verdadero: acudir a su diccionario inglés-castellano y comprobar si el resultado de traducir 'the', 'snow', 'is', 'white', por este orden, da lugar a una verdad castellana.

Pero entonces debe renunciarse a una teoría de la verdad que sea válida para cualquier lenguaje.

Las oraciones abiertas –o funciones proposicionales simples, expresiones como "x es blanca", donde x es una variable- son los componentes elementales del lenguaje para el que se define la verdad; no son ni verdaderas ni falsas en sí mismas, sino satisfechas por unos objetos y no satisfechas por otros.

Una función proposicional compleja es el resultado de combinar mediante conectivas lógicas funciones proposicionales simples; cada función compleja se satisface en función de la satisfacción de sus componentes, según reglas semánticas especificadas –por ejemplo, '"x no es blanca" es satisfecha por un objeto si y solo si ese objeto no satisface "x es blanca"';'"x es blanca o x es roja" es satisfecha por un objeto si y solo si el objeto satisface alguno de sus componentes'-.

Una oración cerrada –o sentencia- es una función proposicional con nombres de objetos en el lugar de las variables o sin ninguna variable no cuantificada lógicamente; las oraciones cerradas son las que pueden ser verdaderas o falsas.